A Human Communication Network Model

Abstract

A number of attributed formation models based on ErdosRenyi and Barabasi-Albert random graph models are presented. One of them is a Human Communication Network (HCN) model based on time restrictions on face-to-face communication. Construction of this weighted network requires a few numerical parameters and allows to transform any unweighted node attributed network into weighted. This transformation helps solving numerous problems in Network Analysis such as community detection, network topology inference, etc. Understanding nature of human communication networks allows to solve many practical problems starting with fast spreading any information and innovation through the networks and ending with detecting key people, collaboration with whom helps achieving di erent goals.

Keywords

• SocialNetworks Community Detection Attributed Networks Node Partition Random Graphs

-

Network Analysis is an area of research that has been studied intensively lately. Researches investigate structural characteristics of di erent networks, network formation models, and many other related questions. Among a variety of networks, social networks, which re ect a diversity of people relationships, are a priority [5], [7]. Study of social networks is important since it helps understanding how our world is organized, what place each of us takes in it, how this situation a ects us and how the knowledge can be used to achieve our goals. Social networks are characterized by heterogeneity of nodes and edges, sparsity, high average clustering coe cient, small average shortest path length and power-law degree distribution, existing observable and tightly bound groups of elements called communities [5]. Most of these properties are united in "smallworld networks" and "scale-free networks" concepts [1],[4]. Many attempts have been made to construct social networks, but still no satisfactory solution to simulate all the listed properties is found [1],[4],[5]. It is also important to nd e cient ways of these community detection (CD) [6],[8]. We believe that the key

- 34 in qualitative CD in social networks is in using the heterogeneity (making them multi-layer ones) and study the issue of such networks formation. 2

De nitions and Notations

De nition 1. [6] A social network is a hybrid graph, which is represented in the form:

G = (V; E; ; 0); ( 1 ) where V is the set of nodes (the social network's users), E is the set of edges (these users relationships), and 0 contain an information about attributes related to each node v 2 V and each edge fu; vg 2 E, respectively. The network represented in the form ( 1 ) is an attributed network if [ 0 6= ;. So, any attributed network representing individuals' relationships is social. Let 2 IRn K ; 0 2 IRm K0 hence V; E are of size jV j = n; jEj = m. Initially, we consider an unweighted node-attributed network G = fV; E; g, K 1. Then we assign weights to its edges (decorate the edges) and come to consideration of a weighted network Gw = fV; E; ; 0g with 0 being a matrix-column of edge weights (K0 = 1). Gw is a node-edge-attributed and used then for CD. Introduce some notations: G[:] = fV; E[:]; g - is an unweighted node-attributed network with an adjacency matrix B[:] = (b[i:j]) 2 IRn n. After decoration E[:] by weights, the new weighted network is denoted by Gw[:] = fV; E[:]; ; 0g and its weighted adjacency matrix (WAM) - by A[:] = (a[i:j]) 2 IRn n.

The node degree d[i:] of a node vi 2 V in G[:] is the number of its incident edges: d[i:] = jNi[:]j where Ni[:] = fu 2 V : u $ vi; fu; vig 2 E[:]g. The node strength s[i:] of vi 2 V is a sum of weights of its incident edges in G[:]. In terms of adjacency and weighted adjacency matrices, these values are: d[i:] = Pj b[i:j], s[i:] = Pj a[i:j]. A network cover is a division of the network nodes C = fClg satisfying SL l=1 Cl = V . If in the division the node clusters Cl; l 2 JL = f1; :::; Lg, are pairwise disjoint, then it is called a network partition.

Assume that the nodes are decorated by K discrete attributes fAT kg, = (atik) where atik is the value of AT k for a node vi, and there are Lk di erent values of AT k. Let AClk 2 V be a set of nodes with l-th value of AT k. We call it a node attribute cluster (AC) and denote a G-partition into ACs related to di erent values of AT k by ACk = fAClkgl2JLk (nlk = jAClkj). Let G[:]k be a G[:]subnetwork related to AT k. A sum of unweighted networks fGkgk of the same node set V is an unweighted network G = fV; Sk Ek; g. A linear combination of weighted networks fGwkgk of a node set V is a weighted network Gw = fV; Sk Ek; ; 0g with a WAM A = P IR are coe cients of this linear combination. Let !(G[:])kbek Adeknwotheedreafwekigght of a network G[:] (!(G[:]) = Pij aij ). A network of a weight one is a normalized network. The networks' linear combination is a weighted network sum if

Gw = X W k Gwk where fW kg > 0; X W k = 1: ( 2 ) k

k Let us consider a social network. Suppose that, in addition to basic information about the node and edge sets, there is available some extra information about the nodes and edges features (social semantic networks are highly helpful here [2]). These additional characteristics are called attributes and the procedure of their complementing is decoration of the network [3], [5] resulted in creation of an attributed network [8]. Applying CD on the network we, typically, get communities closely related to one node attribute and this dominant attribute does not allow us to observe communities in other layers related to the rest, less important, node attributes. For instance, in the humankind network the dominant attribute would be belongingness to families. If we are interested in study communities, say, in work place, then the family division is an obstacle on this way. However, if it is possible to transform the network into weighted, moreover, to assign edge weights to each layer subnetworks of the multi-layer network, the problem of multi-layer CD (MLCD) can be solved. For that we just detect the dominant attribute and extract the corresponding subnetwork from consideration repeating then the procedure on the remaining network.

The crucial part of the approach is constructing edge sets of the one-layer subnetworks and distributing weights within them. The rst one is a problem of the attributed network formation considered in Sect.4.1 (the edge inference problem [5]), the second one is the edge attribute inference problem [5]. The last one we solve for a social network of people face-to-face communication in Sec.4.2. 4

Human Communication Network Models

At this section we touch formation of attributed networks. We are wondering how an attributed network ( 1 ) is formed if the information about nodes V and their attributes is known. In other words, we review formation of an edge set E and its attributes 0 and refer to them as Problems 1 and 2, respectively. 4.1

Attributed Network Formation

We consider a number of ways to solve Problem 1. For convenience, we interpret the presented network formation models in terms of communication of people spending a time together during common activities/interests (AIs). Here nodes are people and their AIs are the nodes' attributes.

Model 1 - an association network model. An association network Ga [5] is an example of an attributed network where links exist between any nodes with common attributes. It can be interpreted as a network of virtual contacts of people with common interests where supporting such contacts does not need anything.

The auxiliary network Gwk corresponds to each activity/interest (AI) AT k; Gw is representable as a weighted network sum ( 2 ) of K networks, which are collections of complete graphs: Gwk = Knlk : Thus the network Ga is a cover of l2[JLk K overlapping V -partitions by a disjoint union of complete graphs. Model 2 - an attributed networks model based on Erdos-Renyi Model. Suppose that for existing an edge a similarity of node attributes is necessary, but not enough because of randomness. Similar to Model 1, we represent the network Gw by ( 2 ). Edges in Gwk are created randomly with probability plk between two nodes vi; vj sharing the l-th value of the attribute AT k. Hence Gk is a node partition by Erdos-Renyi Random Graphs (ERRGs) [4]: Gwk = ERRG(plk; nlk) l2[JLk and the resulting network Gw is an overlapping of K partitions by ERRGs. In terms of human communication, Model 2 simulates a real situation where a group of people is formed simultaneously. Contacts of each user occur randomly without analysing any prior information due to its inaccessibility. The communication can be established on a regular basis only if these people actually have common interests. Di erent type of contacts are formed independently. Model 3 - an attributed networks model based on Barabasi-Albert Model. In comparison with Model 2, here we review a situation where a group of people is formed gradually. First of all, group members aspire to contacts with popular and authoritative colleagues in each area of expertise. First, these contacts are formed for the most important AIs, then for the less signi cant. A chance to clarify common interests is higher if the contact already exists. As before, Gw is a weighted network sum ( 2 ). fGwkg are formed consecutively by k in accordance with decreasing priorities of node attributes. For each k an edge set Ek is formed between nodes with the same value of AT k consecutively k by i with probabilities depending on degrees of all preceding nodes fdi0 gi0<i and parameters pk; p0k (pk p0k) for new and previously established contacts. There are many ways of a generalisation to attributed networks of BarabasiAlbert Preferential Attachment Model [1]. For instance, each auxiliary network Gk is formed as follows: disjoint subsets of nodes of di erent ACs are connected by preferential attachment and then the isolated subnetworks are connected forming the whole node partition ACk. These all partitions are united into a cover with respect to node attributes priorities, , and pre-assigned order of the nodes arising. The network layers are dependent regardless we consider the case pk = p0k; 8 k (Model 3.1) or another one (9k : pk < p0k). Model 3.1 simulates a node partition by Barabasi-Albert Graphs (BAGs). Each Gwk can be represented in a manner of Models 1, 2: Gwk = BAG(nlk; lk) where lk is the l2[JLk power of preferential attachment in AClk. 4.2

The Human Communication Model

The models presented in Sect. 4.1 - Model 2 and Model 3 - are able to simulate networks of real, face-to-face contacts implying requirements to spend time for keeping in touch. Suppose an edge set E was formed according to Models 2 or 3. To nish the network Gw formation, Problem 2 has to be solved and the matrix 0 be formed. Here we present a way to distribute edge weights according to assumptions typical, in our opinion, for real people interaction. We will refer to the obtained network as a Human Communication Network (HCN). The HCN model assumptions. Condition 1. People AIs had already formed; Condition 2. Connections between people are possible if they have common AIs; Condition 3. Each person distributes uniformly the time tk allotted for supporting a contact related to the AI AT k between friends of this interest; Condition 4. For everyone possibility of the communication is restricted by time T . If for a person the time is not enough for supporting his/her contacts, then the time allotted for supporting a contact related to the AT k and AT k0 is distributed proportionally to tk and tk0 , respectively; Condition 5. If two persons with the same interest are ready to devote time to each other, then, if necessary, they come to a compromise following certain rules. Formalise Conditions 1-5 in terms of the WAM A. We rewrite ( 2 ) in the form: Gw =

X Gw0k; where Gw0k = W k

Gwk: k ( 3 ) ( 4 ) ( 5 ) ( 6 ) In addition to Gw satisfying Conditions 1-5, we introduce networks Gw , Gw0 satisfying Conditions 1-3 and 1-4, respectively.

Similarly to the ( 3 ), Gw and Gw0 are representable as networks sums: Gw = Pk G k; Gw0 = Pk G0 k where G k; G0 k are subnetworks of Gw and Gw0 related to AT k. Respectively, the following holds for the corresponding WAMs: A =

X A0k; A = X A k; A0 =

X A0 k: k k k Let a set of vi; vj common attribute values be found as follows: Eij = fk : atik = atjkg JK : Then Ni[:]k = fvj 2 Ni[:] : k 2 Eij g is a set of vi-neighbours with the same AT k-value as vi in G[:]. We expand the notations of the node degree and strength from the set Ni[:] into the sets fNi[:]kgk: a) d[i:]k = jNi[:]kj is the node attribute AT k-degree of vi 2 V in G[:]; b) s[i:]k = Pvj2Ni[:]k a[i:j]k - is the AT kstrength of vi in G[:]. Respectively, the node strength in G[:] is s[i:] = Pk s[i:]k. 1. We start with assigning edge weights in Gw : (a) Condition 1 says that the network Gw is decorated by discrete attributes

AT k and the matrix is known; (b) Condition 2 means that the links are formed only by similarity of the node's attributes, hence if i; j : Eij = ; ) fvi; vj g 2= E. (c) Condition 3 allows to determine the ratio of A k-elements: if i; j; j0; k; k0 such that atik = atjk; atik0 = atjk00 , then atijk tk aijk00 = tk0 : Since there is no restrictions on the communication time in Gw , it implies that all of the contacts are supported at the appropriate level. So, the weights in Gw ; Gw k can be assigned with respect to the maximal needed time tk: 8i; j : k 2 Eij aijk = tk; aij =

X tk: Notice that A is symmetric thus Gw is undirected. The communication time of each person depends on the number of the contacts of each type therefore the node strengths in Gw k, Gw are de ned as follows: si k = diktk; si = Pk;j aijk = Pk si k = Pk diktk: In terms of the HCN model, the values si ; si k can be interpreted as the time that a person i could devote for the communication overall and for the particular AI, correspondingly. 2. Moving on to the network Gw0 , we add Condition 4 - the time restriction to the network Gw . This condition determines how much time a person i is ready to spend for supporting each AI-contact depending on his/her priorities and the number of these contacts. It can be expressed as the restriction on node strengths by T -value: 8i s0i T . If it holds, then the above restriction holds and Gw0 = Gw , otherwise the weights aijk are scaled to meet the time restriction:

a0ijk = i aijk where the scaling parameter i depends on the node i strength: i = min 1; sTi : Substitution ( 7 ) into ( 5 ) yields: aa0i0ijj0kk0 = ttkk0 ii = ttkk0 : It means that each person distributes his/her own time independently from each other and guided common priorities W accumulated in t = (tk): W = t=jtj. Find the WAM of Gw0 by ( 4 ),( 7 ):

0 aij =

X a0ijk = i k

X aijk = i aij : k ( 7 ) ( 8 ) The weights a0ij , a0ji determine how much time a person i is ready to devote for communication with a person j and vice versa. It is clear that normally these are di erent values, a0ij 6= a0ji. Thus the network Gw0 is directed that does not display a face-to-face communication. 3. To describe the real situation, we consider constructing the nal network Gw from Gw0 . By adding Condition 5, the abstract directed network Gw0 is transformed into the undirected Gw with weights equal to time that both persons - i and j - actually devote to each other. The weights are obtained as a result of a compromise between these persons who are ready to spend together not the same time.

Let persons i and j have a real contact (Eij 6= f;g) and are looking for a compromise (a0ij 6= a0ji). The result of their common decision can be expressed as function of these weights aij = f (a0ij ; a0ji): The function f (:) can be chosen in di erent way. For instance, we choose a simple averaging: aij = 12 (a0ij + a0ji): Then, by ( 8 ) and due to a symmetry of A , we have: aij = 0:5( i aij + j aji) = 0:5 aij ( i + j ): (9) Distribution of weights within fG0kg is obtained from ( 4 ), ( 6 ), (9): aij = Pk a0ikj = i +2 j Pk aijk = i +2 j Pk2Eij tk = i +2 j Pk tkbikj wherefrom a0ikj = 0:5( i + j )tkbikj ; aikj = a0ikj=W k = 0:5jtj( i + j )bikj : (10) Example 1 - Model 2 simulation. First, we demonstrate a solution of Problem 1 for Model 2 (see Sect. 4.1). Parameters of a simulated node-attributed network G are: the order n = 60, the number of node attributes K = 3, the nodes are divided randomly into fLkgk = f5; 4; 6g attribute clusters of the same sizes: (nlk) = (125; 154; 106). The result of the simulation with parameters (plk) = (0:35; 0:34; 0:56) is shown in Figure 1. Example 2 - HCN Model 2 simulation. We took the unweighted network G from Example 1 and converted it into the HCN-Model 2 network (see Sect. 4.2) decorating edges by weights according to (9), (10). Two values of the time resource T = (T I ; T II ) and the vector t = (t1; t2; t3) = (4; 3; 2) are used. The vector of priorities of AIs is W = j((44;;33;;22))j = (0:45; 0:33; 0:22). We constructed two networks GwI ; GwII corresponding to T I ; T II . The time restrictions are chosen in the following way: a) in the network GwI for majority, 80%, of people the time T I is su cient to support their contacts completely; b) for the network GwII the situation is opposite - most, 80%, of people should distribute their time resource T II . For the simulated in Example 1 network these parameters are T = (56; 40). In Figures 2-3 we can see the resulted HCNs and observe that edge weights in GwI are more heterogeneous than the ones in GwII . Most likely, the reason is in absence in GwI , in most cases, of necessity to redistribute the time resource. After normalizing Gw, the weights of the subnetworks fGwkg are (!(Gwk)) = (0:772; 1:330; 0:962), hence they are all not normalised and Gw2 is the "haviest".

Results of community detection. CD on G does not show community structure in the network whilst CD on Gw quite accurately yields the partition AC2 into ACs related to AT 2, namely, in 80% of cases two ACs of AC2 were detected correct, rest two - with one error each in GwI . 5

Conclusions and Future Work

The presented Human Communication Network (HCN) model demonstrates an approach to reconstructing missing network information about edges and edge weights based on node attributes and assumptions on nature of interaction in the networks. To the edge inference problem we apply an extension of ErdosRenyi and Barabasi-Albert random graph models to multi-layer node attributed networks. There is shown that, in spite of interconnection of HCN layers, CD is running better in these networks decorated by weights.

The results we are planning to expand to other kinds of networks and use for designing new MLCD algorithms and solving node attribute inference problems.

References

1. Albert , R. , Barabsi , A.-L.: Statistical mechanics of complex networks . Rev. Mod. Phys . 74 , 47 - 97 ( 2002 )

2. Breslin , J. , Passant , A. , Decker , S. : The Social Semantic Web , 2010 edition. ed. Springer, Heidelberg; New York ( 2009 )

3. Brning , J. , Geiler , V.A. , Lobanov , I.S. : Spectral Properties of Schrodinger Operators on Decorated Graphs. Mathematical Notes . 77 , 858 - 861 ( 2005 )

4. Erds , P. , Rnyi , A : On random graphs, I. Publicationes Mathematicae (Debrecen) . 6 , 290 - 297 ( 1959 )

5. Kolaczyk , E.D.: Statistical Analysis of Network Data , Springer Series in Statistics. Springer New York, New York ( 2009 )

6. Lin , Z. , Zheng , X. , Xin , N. , Chen , D. : CK-LPA : E cient community detection algorithm based on label propagation with community kernel . Physica A: Statistical Mechanics and its Applications . 416 , 386 - 399 ( 2014 )

7. Wasserman , S. , Faust , K. : Social Network Analysis: Methods and Applications, 1 edition . ed. Cambridge University Press, Cambridge; New York ( 1994 )

8. Zhou , Y., Cheng, H., Yu , J.X. : Clustering Large Attributed Graphs: An E cient Incremental Approach . In: 2010 IEEE 10th International Conference on Data Mining (ICDM) , pp. 689 - 698 ( 2010 )