In the paper, networks characterized by vertices with a number of attributes (attributed networks) are studied. The networks cover a wide class of real-world ones, particularly social networks, making them especially attractive for further development. We analyze how the attributed networks are formed and present several mathematical models built based on their specifics and utilizing well-known classes of graphs - full ones, Erdös-Rényi and BarabasiAlbert random graphs. The computational experiment part includes simulation of test networks for all presented formation models, evaluating their metrics, and confirming their social networks properties. Barabasi-Albert graphs' based model best demonstrated these features. The results can be further used in Community Detection, Cluster Analysis, missing network attribute's restoration and other related Network Analysis problems.
Network Analysis (NA) is a research field developed intensively in recent years. Researches in NA study different networks, particularly their social and structural characteristics, investigate statistic and dynamic behaviour of networks, design their formation models, single out their specific features, and solve many other related problems. Among all networks, social ones (SNs) that explore and reflect people and relationships between them are an absolute priority.
Why studying and deep understanding SNs is so important? First of all, it provides an understanding of how the world around us is organized. In turn, this allows us to realize what place we occupy in this global human network and how this understanding and knowledge can be used to achieve our goals. At the moment, many features of social networks have been derived. For example, it is known that in the networks there is a so-called "small-world" effect is observable. It manifests itself in a few handshakes between any two people on Earth. At the same time, despite the sparsity of SNs, dense subgraphs called communities are always present in the networks. Many researchers tried to design an ideal model of a social network. However, their attempts have not been crowned with success so far, although they managed to reproduce every single feature of SNs.
This paper is dedicated to modelling social networks and other ones in which vertices and edges are decorated with some discrete-valued attributes (attributed networks, ATNs). We propose three mathematical models for such networks based on the combination of isolated random graphs associated with different attributes and their values. Then we confirm experimentally that such networks are closer to SNs than the ones known so far.
Let us hypothetically imagine that we aim to study the global network of humanity and its community structure. Assume that we have full information about this network, about its participants, contacts and, most importantly, about the strength of these contacts. Thus, we are given full information about the weighted graph displaying this network. Also, imagine that we have access to the most powerful supercomputer in the world for conducting community detection (CD) for analysis in the global network. Evidently, the result of the CD will be quite predictable and will provide the division of people into families since relative relationships are the strongest.
The result of the CD is fully predictable; it would be a division by families because normally people spend most of the time with their families and because family ties are very strong. However, when we set up the experiment, we expected to get something we did not know before. We expect to see the network from different sides, for example, to see the relationship between friends or colleagues. However, in this global humankind network, many other communities are present. They combine people connected with other commonalities than family ties. In fact, setting the problem of the global community detection, we are generally interested in those hidden communities. We are interested in how to single out groups of colleagues in this network, groups of classmates, people with common interests etc. All these communities will be hidden in the network under the first layer of family relationships. Let us imagine that we managed to single out properly the weighted network corresponding to family relations. Then, having removed this dominant layer from the global network, we come to the next network where other layers of communities such as colleges', classmates' ones become visible and therefore detectable by community detection algorithms (CDAs). Having now analyzed the obtained network, repeated CD in it and associated the derived communities with a certain attribute, it becomes possible to single out a second dominant subnetwork. Now, by subtracting it from the graph, we can detect less significant communities hidden under the subnetwork. In such a way, hidden information in the global network becomes visible and detectable.
In NA terminologies, the human network vertices represent people, and edges reflect relationships between people. Each person is unique, and his uniqueness can be represented by a unique combination of quantitative and qualitative characteristics playing the role of the vertices attributes. The same works for the network's edges since the nature and strength of people relations depend on many things representable by edges attributes. As a result, we move from a consideration of a usual unweighted graph as a mathematical model of social networks to the one with heterogeneous vertices and edges. Such networks are called attributed, and the paper is focused on their study.
There are many issues of the hour related to attributed network analysis such as ATNs' formation models; recovering those attributes that are missing; CD in attributed SNs that utilizes knowledge on a network nature contained in its attributes associated with edges and vertices; interpretation of CDresults, and many other related issues. The later problems were studied in [1, 2], where a notion of a multi-layer attributed network (ATN) was introduced, explored and applied in SN Analysis (SNA). This paper is dedicated to the investigation of the first problem related to ATNs' formation modelling. Its solution is of high importance since this allows a deeper understanding of the nature of social and other ATNs and, accordingly, modelling and solving problems of our interest, such as CD, clustering, restoring networks etc. 2.1.
Networks depicted people relationships are called social (SNs). In a graph associated with the network, users of the network are representable by vertices and the users' contacts - by its edges or arcs. In the graph, people heterogeneity is accumulated in attributes of the vertices, while edges' attributes depict a variety of their relationships.
An SN is defined as the following: Definition 1 [3] A social network is a hybrid graph represented in the form of:
G = (V , E, , ), (
Due to SNs are formed based on human relationships, they have specific features that are not characteristic of other networks, such as production, transport, technological, biological ones, and so on. The specifics are caused by the necessity of humans to communicate. Among them are sparsity, low diameter and average shortest path, while the average clustering coefficient is high. Also commonly, there are a few highly sociable people with plenty of contacts, representable in an SN by high degree vertices (hubs). In contrast, there exist numerous unsociable humans with rare connections depicted by vertices of low degree. It results in a vertex degree distribution (VDD) with a "heavy" tail. Another crucial feature of SNs is in the presence of relatively dense subgraphs (communities). Concepts "small-world networks" and "scale-free networks" accumulate the listed properties [4, 5, 6, 7].
Definition 2 [6]. A small-world network is a graph G , where the distance dist(u, v) between two randomly chosen vertices u, v V grows proportionally to the logarithm of its order n network, i.e.
dist(u, v) log n. (2) (3) (5) (6) (7) L C k 1 k = V , where vertex clusters Ck V , k [L] 1,..., L are pairwise disjoint.
Normally, CD assumes designing a network partition. Two classes of the partitions will be considered – a vertex partitions into communities being an output of any CDA and a network partitions into clusters associated with a certain value of the discrete vertex attribute. By combining all such partitions for all the vertex attributes, a resulting network cover is derived.
Definition 5 A network's cover is a division (4) of the network vertices satisfying (5).
Let [13] E (C, C) be an edge set between vertex clusters C, C V . For C V , let G[C] be a subgraph G induced by C . For the network partition (4), the following notation will be used:
main are high CC and small l ; additional are: a) the presence of many cliques and near-cliques caused by high CC ; b) existence of a relatively short path between most of the pairs of vertices caused by small l ; Definition 3 [7] A network is called scale-free if its VDD is power-law, i.e., a probability p(m) of appearing a vertex of degree m connections is approximated as the following: R1 :p(m) = P(du = m) m ,u V.
Due to the listed features, SNs are of interest to researchers [5, 8, 9]. For instance, when SNs are modelled, the investigations primarily concentrate on reproducing small-world peculiarity (2) and scale-free graphs (3). Much fewer results are on modelling networks with clusters and communities, and even fewer papers consider an issue of simulating all the listed properties of SNs [5, 6, 7]. The real interest is riveted to the area of community detection (CD) [8, 10, 11, 12].
Communities may overlap or not. That is why we consider two types of vertex divisions. Definition 4 A partition of a network is its vertex division
= {Ck }kL : (4) * = {Cl }lL* is a partition G into communities, | Cl |=| G[Cl ] |= nl , l L* , nl = n.
lL*
For a network G , assume that we a given by attributes of vertices and (or) edges besides the standard information regarding its vertex set V and edge set E . Thus, the network is decorated [5,14] by these attributes and therefore belongs to the class of ATNs [15]. The question arises how this additional information on the attributes can be used to understand deeper the nature of the network, in particular, is it helpful in CD? Our idea is that communities derived by CDAs are closely related to a single vertex attribute of an ATN or to their combination of these attributes.
In the current section, we will consider the issue of forming ATNs. We will be interested in how
an ATN (
As introduced in [14], an association network G a is an ATN, where any identical value of an attributes results in creating an edge. Indeed, even if people do not know each other but have a common interest, they are related to each other to some extent. Maintaining the contact, in this case, does not cost anything since this contact is virtual.
With any activity/interest (AI), let us associate a network G k , k K . Assume that networks G k and Gk ( k k ) corresponding to different attributes are formed independently. In terms of [14], the weighted network G w = G a can be represented as a weighted network sum (WNS) G w = wk G k .
kK of K subnetworks being a union of complete graphs:
Thus, G a is a cover of K partitions of V by a disjoint union of complete graphs. Weights of the
network are defined by (8), (
wiajk = (k) W lk if vi , v j E, otherwise 0 (i, j n), (k ) is a normalized factor of G k making its weight equal to 1,
Assume that, for the formation of an edge, the presence of identical attribute values is necessary but not sufficient. Likewise Model I, we form the network G w by formula (8). Edges of the auxiliary G k are formed with a probability plk between two vertices vi , v j with a value atlnk of AT nk . Thus, the network G k will be a vertex partition by Erdös-Rényi Random Graphs (ERRGs) [14]: Gk =
ERRG( plk , nlk ), k K .
lLk
The accumulated network Gw GwII will be a cover, where K partitions by ERRGs are overlapped. Weights of edges of a subnetwork G k are defined as follows wk(II ) = (k) W II ,lk if vi , v j E, otherwise 0 (i, j n),
ij where l Lk : vi , v j AClk ,{vi , v j} E;
Gk = lLk Knlk , k JK .
l Lk : vi , v j AClk .
(8)
(9)
(
lLk
Model II simulates a real situation of establishing human contacts when a group of people are formed simultaneously. They have no opportunity to analyze who of the group members is the most interesting person. As a result, contacts arise randomly, and then they become permanent only if there are indeed commonalities of the people interests. 1
In contrast to Model II, we simulate a situation when the team is formed gradually in the next model. Respectively, new people can analyze who is more influential and interesting in the group from his perspective and establish contacts. formed consecutively as k increases with respect to their weights. For k K , the edge set of the network G k is formed within clusters of vertices with the identical value of AT nk consecutively by i J n with probabilities that depend on degrees {dik }i of all preceding vertices vi ( i < i ) as well as on parameters pk , pk ( pk pk ) for new and earlier established contacts, correspondingly. The model uses Barabasi-Albert Preferential Attachment Model [7] and generalizes it onto ATNs. Another way of generalization is to form each network G k as follows: the disjoint subsets of vertices to link according to the preferential attachment. The resulting subgraphs will create a vertex partition k . Then, these all are united into a multi-layer cover . In contrast with the two above models, the network's layers will be dependent regardless pk = pk ,k K (Model III.1) or the one where k J K : pk < pk (Model III.2).
Model III.1 induces a vertex partition by Barabasi-Albert random Graphs (BARGs). G k can be represented likewise (9), (12) yielding:
Gk = BARG(nlk ,lk ), k K , (15)
lLk where lk is the power of preferential attachment in AClk , l Lk ,k K .
The ATN Models I-III introduced in Section 4 we illustrate by examples of simulations in the IGraph implemented in R. The first one is a simulation of an association network G a (Model I), the second one demonstrates Model II (a network G wII ), and the last one shows Model III (a network G wIII ).
These networks have the following common characteristics: the order is n = 60 , the number of the vertex attributes is K = 3 , the vertices are randomly partitioned into {Lk }k = {5, 4, 6} attribute clusters of equal size (nlk )lLk ,kK = (nk Lk )kK = (125,154,106 ) .
Example 1 - Model I simulation
G a is the weighted network sum of vertex partitions by 5, 4, 6 complete graphs, respectively (see (8), (9)): Ga = 0.5 G1 0.3 G2 0.2 G3 , e.g., G1 = l5 K12 . In Figure 1, one can see the graphs 3 G1, G2 and G , which are partitioned by a disjoint union of complete graphs, along with the corresponding association network G a .
According to (8) and (12), G wII is the following weighted network sum of vertex partitions by random graphs: GwII = 0.5 G1 0.3 G2 0.2 G3 . The result of the simulation with parameters ( plk )lLk ,kK = (( pk )Lk )kK = (0.35 , 0.34 , 0.56 ) is depicted in Figure 2. Here, for example, G1 = ERRG( pl , nl ) = ERRG(0.3,12) and G wII is overlapping of three such partitions by l5 l5 random graphs.
Similarly, for the network G wIII , which is simulated according to Model II, we chose a linear
preferential attachment model ( ( lk )lLk ,kK = ( )lLk ,kK , = 1 ). G wIII is formed by (8), (15)
and shown in Figure 2. Here, for instance, G1 = BARG(
The purpose of this section is to identify to which extend the proposed network models reproduce social networks. For this, we analyze the listed above properties of SNs and make a comparison of them.
We conduct CD for all three simulated networks. Table 1-3 shows the obtained values of modularity along with other metrics related to SNs. One can see that modularity is high enough for subgraphs G1 G3 , namely, M [0.747, 0.833] . At the same time, for the resulting network, this value is much lower due to overlapping the above subgraphs, namely, M (0.393, 0.640) . Only for the third model, the modularity is still high enough and indicates a clear community structure. The CD results on G a , G wII , and G wIII are illustrated in Figures 7-9. Model III: the metrics in GwIII n m l CC M n m l CC
M metric n m 0,75 G 2
0.5 , where n | V | , m | E | ; an average shortest path length (ASPL) l 1
l (u, v) , where l (u, v) is the shortest path length between u, v V ; the average m {u,v}E clustering coefficient (ACC) CC is the local clustering 1
CCi , where CCi n i
2di di (di 1) coefficient of vi V , di , di is the vi -degree and number of edges within a neighbourhood of vi ; M 0.5 auw,v du dv / 2 is the modularity, where du is the degree of u V .
l u,vCl
The densities of the networks G a , G wII , G wIII are a bit lower than the one of a sum of G1 G3 one. The network is the densest with (Ga ) = 0.481 , while the network G wIII is the sparsest having (GwIII ) = 0.082 . Besides, G wII is rather sparse and demonstrates (GwII ) = 0.252 . In all these networks, the ASPL-metric is low, and its values fluctuate around 1.6. The only exception is the network G wIII utilizing preferential attachments, namely, l(G wIII ) = 3.975 . On the other hand, the ACC -value in this network is quite high, namely, CC(GwIII ) = 0.476 . At the same time, in the second network G wII , the value is less - CC (G wII ) = 0.34 .
In the last part of the computational experiment, we analyzed the power-low distribution of vertex degrees in our modelled networks. Figure 4-6 shows that in the resulting networks G a and G wII , the 1 degree distribution differs significantly from the distribution of the subnetworks, particularly in G , and from power-law. Only the latest model G wIII shows in Figure 6 behaviour similar to a power-law distribution. In Figure 6 from the two later plots, it is clearly seen the havier right tail in the 1 accumulated network G wIII than the one in G . The two early plots demonstrate fitting the degree distribution by a linear function after switching to a logarithmic scale. The multiple determination coefficient of the linear regressions gets values R2 (G1) = 0.646 and R2 (GwIII ) = 0.761, respectively. This says that an exponential function fits good the achieved degree distribution of the presented network models. The exponential approximation curve better fits the preferential attachment-based Model III. We can conclude that the AN G wIII is the closest to a SN. It has the highest overall rank for the evaluated SN metrics (see Table 4). In the table, the rank 0 corresponds to the worst-case and 1 - to the best. Also, the accumulation of three partitions by BARGs results in an AN closer to an SN than the graph partitions itself. Also, note that in terms of human communication, the networks G wII and G wIII simulate contrasting situations, where contacts are established absolutely by accident or made fully intend. The real situation is a combination of these two. That is why we propose one more network model G w = W 2G wII W 3G wIII , where ASPL decreases thanks to G wII , while the ACC rises due to the presence of G wIII .
In the paper's scope, decomposition of social and other attributed networks (ATNs) into subnetworks related to single vertex attributes is studied as a way of their modelling. A number of models of ATNs with a finite number of discrete-valued vertex attributes is presented. They utilize famous graph models such as complete, Erdös-Rényi and Barabasi-Albert random graphs. Experimentally, it is shown that the proposed ATN models, particularly the Barabasi-Albert graphbased model, are enable to reproduce most social networks peculiarities. It is progress in comparison with known so far networks models.