Structure and Evolution of One Social Network

Structure and Evolution of One Social Network

Beijing University of Posts and Telecommunications, Beijing, 100876 China

{zhangxiaohang, duyu, liujiqi}@bupt.edu.cn

2

IBM Research China, Beijing, China

liuzhiyu@cn.ibm.com

(MCN) constructed by all mobile phone call records consists Abstract—Social networks have been a key subject of research

in recent years, because they can help to understand the of N=1840857 nodes and L=64614195 links. We filtered out people’s behavior such as information diffusion, decision calls involving other operators, incoming or outgoing, making and social influence. This paper is devoted to the study keeping only those transactions in which the calling and of one large-scale social interaction network by carrying out a receiving subscription is governed by the same operator, systematic analysis of network properties and evolution because we have a full access to the call records of this factors. The network properties include degree distribution, operator, but only partial access to the calls made to clustering coefficient, the stability of the social network to subscriptions governed by other operators. All the other nodes removal. The study of network evolution is based on the operators totally cover 25% market share, so the analysis will changes of network size, probability of becoming one user of

not be biased greatly. The FETION network constructed by

the social network on function of number of earlier neighbors,

communication records of FETION users consists of and the roles of the nodes. This social network is constructed

based on communication records of users from one instant N=124204 nodes and L=1189907 links. We get the data

describing when each customer joined the FETION network, message network.

so we can reconstruct the generation of the FETION network. Keywords-social network; structure; evolution

This paper is devoted to the study of these large-scale

I. INTRODUCTION social interaction networks by carrying out a systematic

Social networks have been a key subject of research in analysis of network properties and evolution factors. We recent years, because they can help to understand the study the structure of FETION network in section 2, people’s behavior such as information diffusion, decision including the degree distribution, clustering coefficient and making and social influence. A social network is a social robustness of removing nodes. We have dedicated section 3 structure made of individuals (or organizations) called to discussion the evolution of FETION network, focusing on \"nodeshe influence of each node during the evolution. And in types of interdependency, such as friendship, kinship, section 4, we conclude our findings.

financial exchange, dislike, sexual relationships, or

relationships of beliefs, knowledge or prestige. Uncovering II. STRUCTURE OF FETION NETWORK the structure and mechanism governing the evolution of

The MCN has a skewed degree distribution with a fat tail social networks is very meaningful. Although some

researchers had obtained some conclusions by analyzing (Fig. 1A), indicating that different customers’ degrees are some large-scale networks [1, 2, 3], more empirical analysis distinct, and a relatively small proportion of customers have of real network are also necessary. We believe that some more neighbors and more call counts. In general, the

customers with a higher degree often play a more important valuable rules are still hidden in the social networks.

In this paper, we present a detailed analysis of one instant role in the process of information diffusion and have a message network constructed from a data set consisting of greater influence on other customers. The degree distribution the communication records of over one hundred thousand of FETION related network (at least one node of any link is individuals. The instant message service is called FETION FETION user) shows the similar shape (Fig. 1B), but it provided by one China mobile telecommunication. FETION decreases more sharply at the first stage than MCN. The supports sending instant message by mobile terminals or degree distribution of FETION network (the two nodes of computer. The FETION’s customers must register firstly for any link are all FETION users) still has long fat tail (Fig. mobile service before they use FETION. The total size of 1C), but the size of neighbors shrinks greatly, the biggest one customers of this mobile company is over 1.8 million, in FETION network is only one fifth of the one in MCN.

Clustering, also known as transitivity, is a typical covering approximately 40% of the population of the city.

Because the long calls (they come from/go to other cities) property of acquaintance networks, where two individuals occupy a little proportion, this network is relatively closed, with a common friend are likely to know each other [5].The which guarantee the validity of the analysis. For the purpose clustering coefficient (CC) of one node i is defined as the of keeping customers privacy, each subscription identifier ratio between 󰝁󰯜 and 󰝇󰯜󱈺󰝇󰯜󰵆1󱈻/2, where 󰝇󰯜 denotes the was replaced by a surrogate key. The mobile call network

978-0-7695-4077-1/10 $26.00 © 2010 IEEEDOI 10.1109/ICICTA.2010.460

406

1

Xiaohang Zhang1, Yu Du1, Jiaqi Liu1, Zhiyu Liu2

P(k)1.0000000.1000000.0100000.0010000.0001000.0000100.000001110100Degree kP(k)1.0000000.1000000.0100000.0010000.0001000.0000100.000001110Degree k100AP(k)1.00000000.10000000.01000000.00100000.00010000.00001000.00000100.0000001B100010000110100Degree k100010000 DCP(CC)1.000.100.0110000.000010.000100.001000.010000.10000Clustering Coefficient CC1.0 FRgc1.00.90.80.70.60.50.40.30.20.10.00.00.10.20.3f0.40.50.6 Figure 1. Network properties and robustness of the large-scale MCN and FETION network. (A) Vertex degree distribution of MCN. (B) Vertex degree distribution of FETION related network in which each link connects at least one FETION user. (C) Vertex degree distribution of FETION network in which all nodes are FETION users. (D) Clustering coefficient distribution of FETION network. (E) Correlation of vertex degree and clustering coefficient. (F) The stability of FETION network to nodes removal. The control parameter f denotes the fraction of removed nodes. The star curve (*) corresponds to the case in which the nodes are removed on the basis of their degrees. The square curve (□) corresponds to the case in which the nodes are removed randomly.

degree of node i and 󰝁󰯜 denotes the number of actual links among the neighbors of node i [3]. The CC distribution of FETION network is shown in fig. 1D. We can find that the CCs of most nodes are greater than 0.1that is greater than average CCs of many real networks. It indicates that there exist a lot of compact clusters in which the nodes communicate closely. The correlation between degree and CC can be illustrated by a scatter plot (Fig. 1E) in which each point represents one node. We can find that the nodes, whose CCs are more than 0.6, have lower degree and the nodes with degree more than 100 mainly locate in the range of CC less than 0.3.

407

Users110000100000900008000070000600005000040000300002000010000007Q107Q308Q1Date08Q3AUsers40000B3000020000100000209Q109Q01020304050Number of earlier FETION neighbors SP(S)0.450.400.350.300.250.200.150.100.05010203040CUsers50000400003000020000100000 D5001020304050Number of earlier FETION neighbors S EInterval (month) Users50000400003000020000100000<11<22<33<44<55<66<7>=7Influence

Figure 2. Evolution of FETION network. (A) Changes of number of FETION users from the first quarter of 2007 to the second quarter of 2009. (B)

Distribution of FETION users on number of earlier FETION neighbors who began to use FETION earlier and are only a step distance. (C) Probability of becoming FETION user on function of number of earlier FETION neighbors. (D) Distribution of FETION users on the registering interval. (E) Distribution of FETION users on the influence levels. (F) Correlation between influence levels and number of later FETION neighbors.

To understand the systematic or global implication of the relationship between the node degree and network structure, we explore the network’s ability to withstand the removal of either high or low degree nodes. To evaluate the impact of removing nodes, we measure the relative size of the giant component R󰭥󰭡󱈺f󱈻, providing the fraction of nodes that can all reach each other through connected paths as a function of

408

the fraction of removed nodes f. We find that removing in descending order of degree from the highest to lowest leads to the network’s sudden disintegration at f󰵌0.53 (star curve in Fig. 1F). In contrast, removing the nodes randomly will shrink the network in a linear way but will not precipitously break it apart (square curve in Fig. 1F). The results describe a fundamental difference between the global roles of the

highest and lowest degree nodes in the connectedness of the social network.

Wherever Times is specified, Times Roman or Times New Roman may be used. If neither is available on your word processor, please use the font closest in appearance to Times. Avoid using bit-mapped fonts if possible. True-Type 1 or Open Type fonts are preferred. Please embed symbol fonts, as well, for math, etc.

III. EVOLUTION OF FETION NETWORK

FETION service was to be launched into market in the end of 2006 and began to attracted users from 2007. We can find that the trend of user development is to increase continuously and became fast more dramatically from the second quarter of 2008 (Fig. 2A). It is consistent with network diffusion effects, i.e. at the start the size of network increases gently, then as the network become bigger, it increases more and more rapid and began to rise at an exponential rate, at last it reaches the limit of the population. Before the rapid increase, there is an accumulation stage (from second to fourth quarter of 2007) that can decide the future of the network, because if the network hasn’t enough nodes in a short term, it maybe shrink and die away.

In order to determine the relationship between the network properties and the user behavior of using FETION service, we need to determine whether local network topology affect user behavior. We analyze whether the cumulative probability P(S) of using FETION service increases with the number of earlier FETION neighbors who began to use FETION earlier and are only a step distance. We can find that there is positive relationship between P(S) and the number of earlier FETION neighbors S (Fig. 2C). When S reaches 50, P(S) can be above 40%. And as shown in Fig. 2B, about 33500 FETION users has no earlier FETION neighbors, indicating that some of them are the most initial users. It is also likely that some of them aren’t the real initial users because some FETION users had churned from the operator and we can only get partial interaction records resulting in an incomplete FETION network. However, most of FETION users have earlier FETION neighbors. This follows the FETION service characteristic that a bigger network can bring more values of communication. From the analysis we can confirm that current local network topology can affect the future generation of the network. The interval between the time point when some FETION user registered to use FETION service and the registering time point of the nearest (whose registering time point is nearest) of its earlier FETION neighbors, can be used to analyze the duration of influence in the network. We can see that most users are influenced in short-term period (Fig. 2D) and only a small proportion of FETION users are influenced in long-term period.

During the generation of FETION network, each FETION user had played a different role. We can measure the influence of the users by evaluating how much they can affect the follow-up generation of the network. The influence of node i is defined as Influence󰯜󰵌∑󰯞󰯝󰭀󰬵1/󰜵󰯝, where node j

(j=1, 2, …, k) is the later FETION neighbor (he/she began to

use FETION later and is only a step distance to node i) of node i and 󰜵󰯝 is the number of earlier FETION users of node j. We can find that the distribution of influence is skewed (Fig. 2E), indicating that some nodes has higher influence than others. The nodes with higher influence level play a more important role in the generation. The positive correlation between the influence level and number of later FETION neighbors is shown in Fig. 2F. However we can find that the influence levels of some FETION users are high, but with a small number of later FETION neighbors, indicating that they have absolute impact on their later neighbors.

IV. CONCLUSIONS

In this paper we devoted to the study of these large-scale social interaction networks by carrying out a systematic analysis of network properties and evolution factors. Through the analysis we can get some following conclusions. The MCN and FETION network all have skewed degree distributions with fat tails. In CC distribution of FETION network, most nodes are greater than 0.1, indicating that there exist a lot of compact clusters in which the nodes communicate closely. And there is fundamental difference between the global roles of the highest and lowest degree nodes in affecting the connectedness of the social network. The size of network increased gently at first and then became fast more dramatically at an exponential rate, showing network diffusion effects. The current local network topology can affect the future generation of the network. During the generation of FETION network, the nodes with higher influence level play a more important role.

ACKNOWLEDGEMENT

This work was supported by Project 70901009 of the National Science Foundation for Distinguished Young Scholars, BUPT_IBM 2009 Joint Project, and the Youth Research and Innovation Program 2009RC1027 in Beijing University of Posts and Telecommunications.

REFERENCES

[1] J.-P. Onnela, J. Saramaki, J.Hyvonen, G. Szabo, D. Lazer, K. Kaski,

J. Kertesz, and A.-L. Barabasi, “Structure and Tie Strengths in Mobile Communication Networks,” PNAS, vol. 104, May 2007, pp. 7332-7336, doi:10.1073/pnas.0610245104.

[2] J.-P. Onnela, J. Saramaki, J.Hyvonen, G. Szabo, M. Argollo de

menezes, K. Kaski, A.-L. Barabasi, and J. Kertesz, “Analysis of a Large-scale Weighted Network of One-to-one Human Communication,” New Journal of Physics, vol. 9, June 2007, pp. 179-205, doi: 10.1088/1367-2630/9/6/179.

[3] G. Kossinet and D.J.Watts, “Empirical Analysis of an Evolving

Social Network,” Science, vol. 311, Jan. 2006, pp. 88-90, doi:10.1126/science.1116869.

[4] D.J. Watts and S.H. Strogatz, “Collective Dynamics of ‘Small-world’

Networks,” Nature, vol. 393, June 1998, pp. 440-442. doi:10.1038/30918.

[5] S. Wasserman, K. Faust, Social Networks Analysis, Cambridge

University Press, Cambridge, 1994.

409