Information Asymmetry Flowing in Complex Network

By Kathleen Austin,2014-09-09 11:27
15 views 0
Information Asymmetry Flowing in Complex Network


     Information Asymmetry Flowing in Complex Network121Shao Chenxi, Dou Huiling, Wang Binghong

    (1. Department of Modern Physics and Nonlinear Science Center,University of Science and 5 Technology of China, HeFei 230027;

    2. Department of Computer Science and Technology,University of Science and Technonlgy of

    China, HeFei 230027)

    Abstract: The concept of information asymmetry in complex networks is introduced on the basis of

    information asymmetry in economics and symmetry breaking. Information flowing between two nodes 10 on a link is bidirectional; its size is closely related to traffic dynamics on the network. Based on

    asymmetric information theory, we proposed information flow between network nodes is asymmetrical.

    We designed two methods to calculate the amount of information flow based on two mechanisms of

    complex network. Unequal flow of two opposite directions on the same link proved information

    asymmetry exists in the complex network. A complex network evolution model based on symmetry 15 breaking is establishedwhich is a truthful example for complex network mimicking nature. The

    evolution mechanism of symmetry breaking can best explain the phenomenon of the weak link, long

    tail theory in complex network.

    Keywords: information asymmetry; symmetry breaking; network model

    20 0 Introduction

    The traditional belief claim that almost all graphs are asymmetrical [1-3], various real

    complex networks also have been shown to have a rich degree of asymmetry [4-7]. As a

    ubiquitous phenomenon, the existence of asymmetry in real networks strongly begs an explanation,

    since existing ingredients, such as clustering effect[8] and preferential attachment[9] dominating 25 the construction of network structures, we try to find the dedicated causes in interpreting the

    origination of asymmetry in real networks.

    The concept of asymmetry is widely used in economics and physics sciences. Information

    asymmetry [10], for example, deals with the study of decisions in transactions where one party has

    more or better information than the other. This creates an imbalance of power in transactions 30 which can sometimes cause the transactions to go awry [11]. If we abstract economic activities

    into a complex network, then the economic information will be carried out asymmetry

    dissemination activities on the network, thereby, this will drive the evolution and development of

    economic networks. The idea can be used in other forms of complex networks to explore the

    dissemination of information law in the same way.

    35 In the network communication process, when the dissemination of information found a

    preferred direction of propagation from some kind of instability, the time and space of spread will

    not be isotropic. Instability plays a role of breaking the time and space symmetry. Network

    information will spread in the form of symmetry breaking. Clustering itself represents a breaking

    of space symmetry, bifurcation breaks the time symmetry. Propagation phenomenon of 40 information asymmetry on complex network, such as, in social networks [12], although people

    want to make friends with powerful men, these powerful persons may not wish to be friendly to

    them; in scientific collaboration network [13], two scientists collaborate, from which they may

    both achieve their aims, however their performance must be different. In the actor network [13],

    two actors are connected so long as they turn up in the same movie, but their individual roles 45 (leading actor or not) which function on preferential connectivity are ignored. Similarly, in world

     airports network, the new airports are more likely to connect to metropolises that hold a high

    Brief author introduction: Shao Chenxi, (1954-),male,associate professor,qualitative simulation,non-stationary

    signal processing,non-linear complex system theory. E-mail:

    - 1 -


    status in both economy and politics. Due to their different importance, their attractions of the two

    endpoints may vary asymmetrically after connecting. The above-mentioned shows the

    phenomenon of symmetry breaking in complex network.

    50 Research on asymmetry of complex networks and nonlinear dynamics was given kinds of

    descriptions in asymmetry and symmetry-breaking on networks. [14]Presenting the regularity of

    symmetry-breaking occurring in neural networks and the symmetry-breaking may result in many

    spurious stable states that affect the properties of the network. [15]Studies in and out degree

    distributions discovered a strong asymmetry, hence, proposed connectivity patterns would 55 invariably be asymmetric and use complex network metrics to predict the persistence of

    metapopulations with asymmetric connectivity patterns.

    Motivated by the fact that evolution plays a crucial role in forming kinds of networks, a

    number of models that evolved the structure and dynamics of networks have been studied. These

    evolutionary network models generally seek to determine the properties of the networks that 60 resulted from the evolutionary mechanism being considered. [13] Propose and study a simple

    asymmetrical evolving network model, considering both preferential attachment and random

    (controlled by probability p). That is, the utility increment Δu?Δ u when connecting node toi i j node j . [16] Given a method to check a statistical asymmetry between incoming and outgoing

    edges and discussed its universality, showing in particular that the giant component is always 65 dense among the oldest nodes but invades only an exponentially small fraction of the young nodes

    close to the threshold.

    One of the ultimate goals of complex network research is to understand the dynamic behavior

    of complex networks, transmission dynamics is one of more esoteric dynamics. Although

    information, news, and opinions continuously circulate in the worldwide social network, the actual 70 mechanics of how any single piece of information spreads on a global scale have been a mystery.

    It is however, far from obvious to find solvable methods that would possibly account for some

    relevant features of information asymmetry. The asymmetry and the evolving nature of the

    networks are likely to be important ingredients for deciphering statistical properties of complex

    networks, and the symmetry-breaking in complex networks may produce new methodologies in 75 information processing mechanisms.

    1 Quantification of Asymmetry Information Flow

    1.1 Clustering index

    Clustering derives quite directly from the problem that the proportion of friends among ones

    friends. Clustering coefficient of a node is the ratio of number of connections in the neighborhood 80 of a node and the number of connections if the neighborhood was fully connected. Clusters have

    much to do with small average path length and clustering coefficient of the network. The

    information will circulate in one node-cluster redundantly, where node-cluster means the graph

    grouped by the node itself and its neighborhood. The clustering coefficient of the node can denote

    the flow ability ( p) of the node among the node-cluster, the degree of the node denotes the fa

    85 split-flow ability ( p), and the information distribution at each node should be direct proportional sf

    to the flow ability and reverse proportional to the split-flow ability. In such a way that: c/k, i i

    where cand kdenotes the clustering coefficient and degree of node i respectively. The amount i i

    of information is proportional to the flow-out node and reverses proportional to the flow-in node.

    Therefore the index of clustering coefficient to count the amount of information flow shows 90

    - 2 -


     k ? c jj ? N (i)i s * * , ? i a = c k(1) ? ij i j

    ?otherwise 0, ?

    Where a is the information flowing matrix, ais flow capacity from node i to node j . ij

    s denotes the strength of node j, the correlation between strength s and degree k of nodes is j ? power-law correlation N (i) is the set of neighbor nodes of node . s ~ k [17-18].i

95 1.2 Preferential attachment index The mechanism of preferential attachment is an important driving force for generating

     evolving scale-free networks, where the probability that a new link is connected to the node x is proportional to k (x) which is the degree of node k . According to resource distribution dynamics of weighted network, we proposed information flow pattern based on preferential attachment: the

    100 information content of the source node flowing to the goal node is direct proportional to

    proportion of the degree of this goal node occupying the degree sum of all neighbor node of the

     source node. The information flowing is given by ?* skk,j ? N (i), i? il ? l?N (i ) (2) a= ?ij ?0,otherwise ? 2 Complex Network of Symmetry-Breaking Model

    There have been many research results about evolution mechanism and network modeling [8, 105

     21-23]. The discovery and proposition of evolution mechanism on complex network such as clustering effect, preferential attachment make the research of complex network more colorful and

     more meaningful. The model of complex network is not limited to early regular network and random network models. Small world and scale-free network models can reflect the characteristics

    of complex network better in reality. 110 Only from the topology point of viewthe networks generated by small-world algorithm is a transition network form regular networks to random networks, p = 0 corresponds to a completely

     regular network, and p = 1 corresponds to a completely random network, the network can be controlled from a completely regular network transiting to the random one by adjusting the value

    of p . The network transition form regular network to random one is the result that the network is 115 gradually breaking the symmetry. Small world network is the phase reaction of symmetry breaking on complex network.

     Moreover, two important evolution rules were proposed in scale-free model: growth and preferential attachment, which is the abstract out of the actual formation of the World Wide Web.

    However, experts pointed out that there are two ambiguities in the BA model. First, the initial 120 network is not completely set, it only shows the N given nodes at the beginning, the situation of links between nodes did not specify; if it is an isolated node, then the preferential attachment is completely unable to proceed, so the simulation always starts from a complete connected graph. Second, when m>1 , adding new connection may result in duplicate links. We look at these two

    125 problem from another point of view: first, the initialization of derived model of BA model is

    defined as the complete graph or random graph at the initial, both methods are feasible, We know

    that the results of model evolution is scale-free networks with power-law distribution. If the initial

    - 3 -


     network is regular network, the scale-free networks with asymmetry are formed by breaking the symmetry, if the initial network is a random network, the network is asymmetry at the beginning

    of the evolution. This indicates symmetry breaking occurs at the beginning and in the process of 130

     the evolution of the network. Complex network found in a preferred direction of propagation in its special bifurcation point from some instability, the evolution of space-time will no longer be isotropic. From the information asymmetry flowing of complex network we speculate that the network

    will be the case of asymmetric evolution. Zheng [13] proposed and studied a simple asymmetrical 135

     evolving network model by introducing utility to describe the attractions of nodes in the work, he pointed the model represents a transition between exponential and power-law scaling. Complex network exist the nature of information asymmetry explains the evolution of the actual network should also be driven by asymmetry. We consider the following variant of the

    evolutionary game for evolving the asymmetry functions of complex network. Specific 140 evolutionary algorithms of complex network based on symmetry breaking:

     N , the number of network nodes m, the number of edges m of I) Set the network size 0 the new node linking with the old network;

     ?) Initialize the network with a complete graph; ?) Growth: add a new node, the old network turn into a new network; 145

     ?) Calculation of the probability of network connectivity; ?) each time adding a new node, the probability of network connectivity changes,

     every cycle is a relatively independent entity, process should be segmentation; ?) calculate information flow generated based on clustering index;

     ?) calculate information flow generated based on preferential attachment index;

    150 ?) clustering index and preferential attachment index simultaneously act on the goal network, each kind of index has generated certain information flow in the network, the total information flow computation is the weighted sum of these

     two kinds of information flow; ?) the sum of in-degree flow as the current capacity of this node at this moment,

    155 the node flow to the network total flow is frequency of each node current capacity; this is link probability of new node linking.

     ?) New links joining; ?) the frequency of node degree is divided into several communities with the

     interval (0, 1); point experiment needed be done in these communities;

     ?) compare values of the random function with the endpoints of each interval,160

     falls in the i -th individual cell, which means that it will be connected with the

     i -th node; ?) Repeat m times, the selected point for three times are different to avoid the

     emergence of duplication links; ?) New point added to the network, the adjacency matrix changed accordingly.165

    ?) Back to ?, and then add a new node, until the network size is N .

    - 4 -


     3 Analysis

     3.1 The phenomenon of information asymmetry on complex network

    There will be a certain flow of information between any two nodes on network; this 170

     information may be specific viruses, speech, etc. However, it can also be trust, influence in the abstract, and so on. The link between nodes driven by many factors, will lead to a phenomenon of

     the asymmetry flow between each pair of nodes. In fact, the flow of information between nodes cannot be symmetrical if the information between each link is the same, then the network will not

    evolve so complicated. We use the Usair [19] network to do an empirical verification, two 175

     information flow quantitative indexes act on the target randomly selected node pairs of 20, 50 and all separately. In Fig.1 (a, b) and Fig.2 (a, b), the bidirectional information flow of one node pair

     probably emerge a wave crest on one polyline and a wave hollow on the other polyline. The contradistinction between the opposite directions shows the asymmetry of information flow

    between the node pairs of the network. 180

     Furthermore, the experiments study the complexity of a single node in the network, the big-degree node, for example. The asymmetry also appeared in the information flow between the out-degree nodes and in-degree nodes. In Fig.1(c) and Fig.2(c), we plot the information flow of all node pairs in the Usair network. We can see a representative node (maybe a hub node or

    big-degree node) of a network is the epitome of the whole network, which behaves complexities 185

    ased on the repetition and superimposition of all nodes. bFig.1 and Fig.2 are very good validation

    for information asymmetry of the complex network. There is certain reciprocal nature of

     information flow between each pair of nodes. 4 x 10 14 A i?>j j?>i 12



     6 Information flow 4


     00 2 4 6 8 10 12 14 16 18 20 n 4 x 10 6 B i?>j j?>i 5 4 3 Information folw 2 1 00 5 10 15 20 25 30 35 40 45 50 n 190

    - 5 -


     5x 10 14 C i?>j j?>i 12



     6 Information flow 4


     0 0 500 1000 1500 2000 2500 n FIG.1. (a) The information flow of 20 node pairs in the Usair network under the clustering index, (b) The information flow of 50 node pairs in the Usair network under the clustering index, (c) The information flow of all node pairs in the Usair network under the clustering index. Red line is the flow of i ? j and node pair i ? j 195 is arbitrary, blue line is the flow of j ? i . In (c) the red line is sorted descending by size and the blue one is the resulting data of flow mapped to the node pairs of the red line. 60 A i?>jj?>i 50 40 30 20 10 00 2 4 6 8 10 12 14 16 18 20 n 70B i?>jj?>i 60



     30 Information Information flow flow 20


     00 5 10 15 20 25 30 35 40 45 50 n

    - 6 -


     250i?>j Cj?>i



     Information 100 flow


     00 500 1000 1500 2000 2500 n

    200 FIG.2. (a) The information flow of 20 node pairs in the Usair network under the preferential attachment index, (b)

    The information flow of 50 node pairs in the Usair network under the preferential attachment index, (c) The

    information flow of all node pairs in the Usair network under the preferential attachment index. Red line is the

    flow of i ? j and node pair i ? j is arbitrary, blue line is the flow of j ? i . In (c) the red line is sorted

     descending by size and the blue one is the resulting data of flow mapped to the node pairs of the red line. 205

     In the Fig.3, A (b) is the sorted information flow by size from node 118 (a node, numbered 118, which is the biggest degree node in Usair network) to its neighbor nodes. A(c) is the opposite

     flow corresponding to the node pair in A (b). A (b) and A(c) illustrate the asymmetry flow between node 118 and flow-in or flow out node. A (d) is the log-log plot of the polyline in A (b).

    210 A (e) is the log-log plot of the polyline in A(c). We can see the flow distribution of one node

    exhibits as a power-law behavior. A (a) is the degree distribution of the neighbor of node 118 in

     the neighbor’s order in A (b). Fig.3 (B) has the same meaning with Fig.3 (A) 5 x 10 74 14 1500 35010 10 A k 118?>j 118?>j i?>118 i?>118 c ea d b 3300 12 10 6 10 2250 10 10 1000 1200 8 10 510 0150 6 10 500 ?1100 4 10 410 ?250 2 10

     3 ?3 0 0 010 10 0 2 4 0 2 4 0 100 200 0 100 200 0 100 200 10 10 10 1010 10 13 350 7 250 10 10 B k 118?>j i?>118 a118?>j i?>118 b c d e 300 6 0200 10 250 5 210 ?1 150 10 200 4

     150 3 ?2100 10 10 100 2 ?3 50 10 50 1

     ?4 0 0 0 010 10 0 2 4 0 2 4 0 100 200 0 100 200 0 100 200 10 10 10 10 10 10 215 FIG.3. (a) The information flow of out-degree node and in-degree node on node 118 under the clustering index, (b)

    The information flow of out-degree node and in-degree node on node 118 under the preferential attachment index.

    - 7 -


     If the value of clustering coefficient of a node is big, then the information flow from the node to the other node of the cluster is fast and busy. A message in the cluster will be circulated, but

     spreading outside the cluster is relatively tortuous. For the nodes with high clustering coefficient

    k , some information in large clusters becomes negligible, but if it due to diversion of degree 220

     spreads outside to the boundaries of clusters, this link is likely to be a weak link. In Fig.4, node 1 and 2 in two different societies, respectively. The clustering coefficient of node 1 and node 2 is 1/2

     and 1/3, the flow of information from node 1 to node 2, the value is 5.169, the flow of information the many communities are showing a weak from node 2 to node 1 is 2.976. These links between

    link in nature. 225 FIG.4. the information flow among node-cluster based on clustering index.

    Weak links are not as stable as strong links, but has a high dissemination speed with high

    efficiency and low cost. A small airport which is located between two big airports would have a 230

     key role to alleviate the airport's passenger traffic pressure. These links between small nodes and big nodes nearly are weakly connections.

     In fact, weak connection plays the same role in the spreading of information dissemination. For example, a circle of friends and family who may know each other; in such circles, information

    exchanging provided by others is always redundant. The piece of information just heard from a 235

     friend or relative after whom had already been heard from another friend, they will talk to each other again about the said topic. The same information performances with different roles in

     different links resulted to an asymmetric flowing of information. Weak links in the information flow have the directional property, that is, weak" in weak links is directional. The reason why the

    weak link has a strong role is because the weak link in the flow of information asymmetry has the 240

     performance of a strong flow "phenomenon. The result of the model algorithm is a complex network with both small-world and scale-free nature, and a better response of the symmetry breaking occurring in the growth process of the network and the asymmetry manifested in the evolution of the network.

     245 3.2 Model results

     3.2.1 Clustering coefficient analysis Experimental results show that the clustering coefficient of the complex network generated by the model is positively correlated to the ratio of clustering factors in the evolution of the

    network. One of the characteristics of small world network is the network clustering coefficient is

    250 relatively large, indicating that small-world networks for the gathering to break the symmetry of

    the relatively large proportion of factors. Concentration by itself represents a lack of spatial

    symmetry breaking.

    - 8 -


    TABLE 1. The clustering coefficient of the mean value number is obtained by averaging 30 implementations. Here,

     we chose the top 10 data listed in the table. The parameter ? for s is fixed as 1. C(0-1) C(0.01-0.99) C(0.1-0.9) C(0.5-0.5) C(0.9-0.1) C(1-0) 1 0.038038 0.054239 0.42056 0.058498 0.34396 0.074534 2 0.045373 0.054195 0.071697 0.044942 0.032371 0.050505 3 0.037485 0.06049 0.079701 0.020199 0.19049 0.048467 4 0.031614 0.061495 0.34412 0.17625 0.86514 0.27048 5 0.034377 0.071917 0.11335 0.10967 0.41711 0.31374 6 0.026931 0.0399 0.11343 0.1039 0.34031 0.065126 7 0.039447 0.063248 0.37953 0.10844 0.18054 0.043545 8 0.036973 0.04582 0.071858 0.039609 0.60583 0.36918 9 0.036463 0.054557 0.077759 0.18068 0.045748 0.62205 10 0.030188 0.12614 0.1017 0.35608 0.29228 0.019005

     Mean value 0.0318 0.0592 0.1298 0.1710 0.3541 0.2739

     255 TABLE 2. The clustering coefficient of the mean value number is obtained by averaging 30 implementations. Here,

     we chose the top 10 data listed in the table. The parameter ? for s is fixed as 1.5. C(0-1) C(0.01-0.99) C(0.1-0.9) C(0.5-0.5) C(0.9-0.1) C(1-0) 1 0.035962 0.05238 0.075129 0.018517 0.049894 0.049257 2 0.034338 0.040864 0.084873 0.049923 0.63589 0.35591 3 0.031566 0.046588 0.21846 0.035222 0.18754 0.11847 4 0.024628 0.05833 0.083718 0.060218 0.37938 0.59933 5 0.031613 0.037782 0.062923 0.0759 0.80442 0.037213 6 0.024055 0.039936 0.3561 0.093898 0.016393 0.04109 7 0.034097 0.055049 0.053331 0.20807 0.42018 0.059919 8 0.031941 0.036682 0.2118 0.04626 0.36722 0.10867

    9 0.031892 0.050486 0.07831 0.36767 0.74858 0.26559 10 0.028797 0.047172 0.15578 0.096449 0.095236 0.06578 Mean value 0.0299 0.0466 0.0974 0.1428 0.3524 0.2082

     C(0?1) A C(0.01?0.99) C(0.1?0.9) 0.9 C(0.5?0.5) C(0.9?0.1) C(1?0) 0.8 0.7 0.6 0.5 0.4 clustering cofficient 0.3 0.2 0.1 00 5 10 15 20 25 30 times

     2600.9 C(0?1) C(0.01?0.99) 0.8 C(0.1?0.9) C(0.5?0.5) C(0.9?0.1) 0.7 C(1?0) 0.6 0.5 cofficient 0.4 clustering 0.3 0.2 0.1 00 5 10 15 20 25 30 times FIG.5. (a) The track of clustering coefficient for 30 times uninterrupted evolution of network for ? =1, (b) The track of clustering coefficient for 30 times uninterrupted evolution of network for ? =1.5.

    - 9 -


     Experimental results show that the model generates a complex network of clustering

    265 coefficient with the concentration factor is the evolution of the network share are related. One of

     the characteristics of small world network is the network clustering coefficient which is relatively large, indicating that small-world networks for the gathering to break the symmetry of the

     relatively large proportion of factors. The peak and valley values in the Fig.5 above are the point of a major restructuring in the

    evolution of complex networks , the red line means the bigger proportion of clustering in the 270

     breaking, the more prominent the gap between peak and valley. This image also shows that symmetry breaking is the randomness of the occurrence.

     Clustering itself represents a kind of spatial symmetry breaking. Experimental results show that the symmetry breaking based clustering nature is a growth evolution driver of complex

    network. 275

     The evolution mechanisms of complex networks are diverse, if mechanism was enforcing single, there will be anomalies.

     3.2.2 Degree distribution analysis Statistical studies have shown that actual network with long-tail distributions [24-27] and

    truncated nature [28-29] had long been found, but few have analyzed its causes. Symmetry 280

     breaking mechanism is expected to explain these phenomena. Because of symmetry breaking, Matthew effect [30-32] which lead to the complete power-law distributions can be effectively

     controlled, break the advantages of some big nodes; balance the capacity of all nodes linking. The study provides a more realistic portrayal of the actual network model, the actual data distribution

    in the truncated tail and so on may also be reflected in the network model. 285 In Fig.6, we plot the degree distribution with respect to different values of a and b in the asymmetrical evolving network. The result of experiment by only preferential attachment

     factor( as shown in Fig.6(A)) is relative standard scale free network; however, many actual structure of the networks is the power law distribution with a long tail, so along with

    clustering-asymmetry is more in line with the laws of the actual network, as shown in the Fig.6(C), 290

    (D) and (E).

    In Fig.7, we plotted the contradistinction of the degree distribution with respect to different

    values of a and b and the simulated result of mean-field approach [33]. The distribution of

    a=0,b=1 (?) and a=0.01,b=0.99 (?) are in line with the mean-field result.

    - 10 -

Report this document

For any questions or suggestions please email