# A Study on the Relationship between Connecting Different Types of Nodes and Disassortativity by Degree

Authors: Chengdong Dong
Journal: Mathematical Problems in Engineering
 (2010)

---

## Abstract

This paper investigates how to change the disassortativity of the whole network by connecting nodes of different types in two communities. A model connecting two multi-center networks is studied to see if analytical results are achievable. There are three main methods to connect two multi-center subnetworks depending on whether the connecting nodes are centers: (1) connect the centers of one sub-network to noncenter nodes of the other sub-network, (2) connect the centers of the two sub-networks together, and (3) connect non-center nodes of the two sub-networks. The results show that the disassortative property of a single multicenter network can be maintained in scenarios (1) and (2) above, but the disassortativity is changed in (3). In conclusion, either assortativity or disassortativity is achievable by connecting nodes with different degree properties in an ideal network constructed from two communities with similar network topology.


---

## Body

## 1. Introduction

The study of complex networks originated from the paper “Collective Dynamics of “Small World” Networks” [1] on Journal Nature 1998 by Watts and Strogatz, which unveils the small world effect. Small-world networks exhibit both the highly clustered property as in regular lattices as well as having small characteristic path length as in random graphs. In 1999 Barabasi and Albert published the paper “Emergence of Scaling in Random Networks” [2] in the journal Science. Because the emergence of scaling does not have apparent characteristic length, this type of networks is also called scale-free networks. Since then, a lot of researches have been focused on the “scale-free” property of real-world networks, such as power-law degree distributions. Subsequently, other aspects of complex networks including mechanism of epidemic spreading [3–6], synchronization property [7–11], cascading failure [12–14] have also been studied.Besides those generally acknowledged properties, mixing pattern is one of the important research subjects of complex networks as well. The characteristic property of nodes in a network preferentially connecting to those which are similar to themselves is called assortative mixing. On the contrary, the phenomenon that nodes in a network preferentially connect to others unlike themselves most is called disassortative mixing. A lot of research shows that technological and biological networks generally possess disassortative characteristic while social networks usually possess assortative characteristic.In realistic applications [15], assortative networks (such as the social network of film actors) tend to percolate more easily than their disassortative counterparts (such as the Internet topology [16]), and they are also more robust to vertex removal.The recent research on disassortativity is based on the following two main methods:(1) Assortativity coefficientr is simply the Pearson correlation coefficient of the degrees at either ends of an edge(1.1)r=M-1∑ijiki-[M-1∑i(1/2)(ji+ki)]2M-1∑i(1/2)(ji2+ki2)-[M-1∑i(1/2)(ji+ki)]2,
where ji, ki are the degrees of the nodes at the ends of the ith edge, with i=1,2,…,M.Assortativity coefficientr lies in the range -1≤r≤1. And if r>0, the network is assortative. On the contrary, if r<0, the network is disassortative [15].(2)knn(k) is defined to be the average neighbor connectivity of a node with degree k.(1.2)knn(k)=∑k′=1kmax⁡k′P(k′/k),
where P(k′/k) is used to describe the conditional probability that my network neighbor is of degree k′ given that I am of degree k [16].This degree-degree correlationknn(k) gives a one-parameter curve. if knn(k) increases as the degree k increases, the network has assortative property. Otherwise, if knn(k) decreases with k, the network is disassortative [17].This paper will focus on finding why a network shows assortativity or disassortativity, which has not been discussed extensively. It is known that complex networks also have community structure, which brings up a natural question: how does the interconnection between communities affect the assortative property of the whole network? In general this kind of questions can only be solved by numerical method, but in this paper we will try to give analytical explanations. Based on our previous work of multi-center networks, in this paper a multi-center network with the number of nodesN and centers l  is considered as a community in a larger network. Thus, the impact of the interconnection on assortativity can be analytically discussed.The rest of the paper is organized as follows. In Section2, the model of multi-center network structure and three ways of interconnection between two multi-center networks will be introduced. From Section 3 to Section 5, we will present the study on networks via connecting centers to non-center nodes, centers to centers, non-center nodes to non-center nodes, respectively. The analytical conclusion will be discussed in Section 6.


## 2. Models

Firstly, we will introduce the concept of multi-center network. In this paper, a multi-center network [7] is defined as a network with N nodes if the following conditions are satisfied:(i)
There arel (l≪N) nodes, any of which connects to the other N-1 nodes, and(ii)
any of the remainingN-l nodes only connects to the above l nodes, and there is no edge between the remaining N-l nodes.In this multi-center network model, thel nodes are called center nodes. The degree of the centers is N-1 due to condition (1.1), while the degree of non-center nodes is l due to condition (1.2). And a single multi-center network is obviously disassortative by degree under the presupposition l≪N.A new ideal network is defined as two interconnected multi-center sub-networks. They are denoted as I and II. The number ofnodes isN1 and N2 respectively. And the number of centers is l1 and l2. To connect sub-networks I and II means connecting m1 nodes of I to m2 nodes of II such that a more complex network is constructed. These m1+m2 nodes are called connecting nodes. Depending on whether they are center nodes or not, there are four possible ways of interconnection [8, 9]:(i)
connect centers of I to centers of II;(ii)
connect non-center nodes of I to non-center nodes of II;(iii)
connect centers of I to non-center nodes of II or connect centers of  II to non-center nodes of  I; and(iv)
connect any arbitrary nodes of I to arbitrary nodes of  II.The simplified ideal network model studied in this paper assumes either that one of the two communities is a multi-center network in which the number of nodes isN and the number of centers is l, or that both communities have the exactly same structure. We will discuss the assortative property by the degree of the new ideal network constructed by the previous three ways of interconnections. The fourth method in the enumeration will not be consideredfor the moment, as it is a bit more complex to discuss and goes beyond our topic in this paper.


## 3. The Ideal Network Connecting Centers to Non-Center Nodes

To connect sub-networks I and II means to connectm1 centers of I to m2 non-center nodes of II, and so 0<m1≤l, 0<m2≤N-l.The whole set of nodes in the network can be categorized into four types by the degree property:Type 1.
If the connecting nodes are excluded, non-center nodes in sub-networks are of degreel, and there are 2N-2l-m2 nodes of this type in the whole network. The number of links belonging to nodes of Type 1 is l(2N-2l-m2), where(1)
the number of links to non-center nodes with connecting nodes excluded (i.e., which have degreel) is 0,(2)
the number of links to connecting nodes of sub-network II (i.e., which have degreel+m1) is 0(3)
the number of links to centers with connecting nodes excluded (i.e., which have degreeN-1) is (l-m1)(N-l)+l(N-l-m2)(4)
the number of links to connecting nodes of sub-network I (i.e., which have degreeN-1+m2) is m1(N-l)Therefore,
(3.1)p(l/l)=0,p(l+m1/l)=0,p(N-1/l)=1-m1(N-l)l(2N-2l-m2),p(N-1+m2/l)=m1(N-l)l(2N-2l-m2).Type 2.
Connecting nodes of sub-network II have degreel+m1, and there are m2 nodes of this type in the whole network. The number of links belong to nodes of Type 2 is m2(l+m1), where(1)
the number of links to non-center nodes with connecting nodes excluded (i.e., which have degreel) is 0(2)
the number of links to connecting nodes of sub-network II (i.e., which have degreel+m1) is 0(3)
the number of links to centers with connecting nodes excluded (i.e., which have degreeN-1) is l·m2(4)
the number of links to connecting nodes of sub-network I (i.e., which have degreeN-1+m2) is m1·m2Therefore,
(3.2)p(l/l+m1)=0,p(l+m1/l+m1)=0,p(N-1/l+m1)=ll+m1,p(N-1+m2/l+m1)=m1l+m1.Type 3.
Centers but not connecting nodes of sub-networks have degreeN-1, and there are 2l-m1 nodes of this type in the whole network. The number of links belong to nodes of Type 3 is Δ1=(N-l)(l-m1)+(N-1)l-(1/2)m1(m1-1), where(1)
the number of links to non-center nodes with connecting nodes excluded (i.e., which have degreel) is (l-m1)(N-l)+l(N-l-m2)(2)
the number of links to connecting nodes of sub-network II (i.e., which have degreel+m1) is m2·l(3)
the number of links to centers with connecting nodes excluded (i.e., which have degreeN-1) is (l-m1)(l-m1-1)/2+l(l-1)/2(4)
the number of links to connecting nodes of sub-network I (i.e., which have degreeN-1+m2) is m1(l-m1)Therefore,
(3.3)p(l/N-1)=(l-m1)(N-l)+l(N-l-m2)Δ1,p(l+m1/N-1)=m2lΔ1,p(N-1/N-1)=(l-m1)(l-m1-1)+l(l-1)2Δ1,p(N-1+m2/N-1)=m1(l-m1)Δ1.Type 4.
Connecting nodes of sub-network I (i.e., which have degreeN-1+m2) are not only centers but also connecting nodes of sub-networks, and there are m1 nodes of this type in the whole network. The number of links to nodes of Type 4 is m1(N+m2-(1/2)m1-1/2), and let Δ2=N+m2-(1/2)m1-(1/2), where(1)
the number of links to non-center nodes with connecting nodes excluded (i.e., which have degreel) is m1(N-l)(2)
the number of links to connecting nodes of sub-network II (i.e., which have degreel+m1) is m1·m2(3)
the number of links to centers with connecting nodes excluded (i.e., which have degreeN-1) is m1(l-m1)(4)
the number of links to connecting nodes of sub-network I (i.e., which have degreeN-1+m2) is (1/2)m1(m1-1)Therefore,
(3.4)p(l/N-1+m2)=N-lΔ2,p(l+m1/N-1+m2)=m2Δ2,p(N-1/N-1+m2)=l-m1Δ2,p(N-1+m2/N-1+m2)=m1-12Δ2.There are four kinds of degrees in the network, which arel, l+m1, N-1, N-1+m2. Thus matrix {p(k′/k)} is as follows:(3.5)(001-m1(N-l)l(2N-2l-m2)m1(N-l)l(2N-2l-m2)00ll+m1m1l+m1(l-m1)(N-l)+l(N-l-m2)Δ1m2lΔ1(l-m1)(l-m1-1)+l(l-1)2Δ1m1(l-m1)Δ1N-lΔ2m2Δ2l-m1Δ2m1-12Δ2).Then we can obtain the expressions of average neighbor connectivity to nodes with the degreel, l+m1, N-1, N-1+m2 respectively, which can be listed as follows:(3.6)knn(l)=[1-m1(N-l)l(2N-2l-m2)](N-1)+m1(N-l)l(2N-2l-m2)(N-1+m2)=(N-1)+m1m2(N-l)l(2N-2l-m2),knn(l+m1)=(N-1)+m1m2l+m1,knn(N-1)=1Δ1[(N-1)(l2-l+12m1-12m12)+(N-l)(2l2-lm1)-m12m2+2lm1m2],knn(N-1+m2)=1Δ2[(N-1)(2l-12m1-12)+(32m1-12+l)m2+l-l2].Firstly, from (1.1), the expression of assortativity coefficient r of this ideal network can be obtained. It is evaluated from the estimates of the number links connecting different nodes (cases Type 1 to Type 4). Since the expression is complex and irregular, it will not be listed here. Secondly, based on (1.2), the projection of the degree-degree correlation can apply to this ideal network step by step as shown above.It is difficult to analyze variation range ofr and the varying trend of knn(k) with k due to the complexity with their expressions. Instead, we introduce numerical methods for analysis. Assume that N=1000, l=20, m1=αl, m2=β(N-l), where α shows the proportion of connecting nodes in centers of sub-network I, and β shows the proportion of connecting nodes in non-center nodes of sub-network II and α,β∈(0,1]. The relationships between r, knn(k) and m1, m2 can be studied in the three-dimensional space.In this way, we can study how assortativity coefficientr and degree-degree correlation knn(k) vary along with the variety of α,β. Not only the research is further simplified, but also the values of α, β are more practical and meaningful.Under this assumption, the assortativity coefficient of single multi-center network has a perfect value to show its disassortative property, wherer=-0.9810. Figure 1 is a three-dimensional graph of the relationship between r and α, β under the assumption that N=1000, l=20. The trend how r varies along with α, β can easily be observed.Figure 1
Relationship betweenr and α, β when N=1000, l=20(x=α,y=β).It can be obtained that assortativity coefficientr varies between −0.9810 and −0.7853 along with α, β in the ideal network connecting centers of sub-network I with non-center nodes of sub-network II. In addition, the range of variety is finite. Besides, r in this case almost exceeds the value of single multi-center network (r=-0.9810). It shows that although the ideal network is disassortative, it is already more assortative, to some extent, than the single multi-center network.The reason is that some of nodes with low degree (i.e., part of non-center nodes in sub-network II) increase their links, which increases the average degree of these nodes that connect to centers with high degree. Subsequently, the disassortativity becomes lower. But meanwhile the average degree level of centers in sub-networks increases. When taking both situations into account, the whole network is still constructed by connecting nodes with high degree and nodes with low degree. Therefore, the network is disassortative overall.Similarly under the assumption thatN=1000, l=20, Figure 2 shows two types of relationship between knn(k) and degree k in the ideal network with this connecting way.(a)knn(l)>knn(l+m1)>knn(N-1)>knn(N-1+m2). (b) knn(l)<knn(l+m1), knn(N-1)<knn(N-1+m2), but knn(l)≫knn(N-1+m2).
(a)(b)In the ideal network connecting centers of sub-network I with non-center nodes of sub-network II, nodes with the degreel, l+m1, N-1, N-1+m2 have the average neighbor connectivity knn(l), knn(l+m1), knn(N-1), knn(N-1+m2), respectively. There are two types of scenarios on average neighbor connectivity as described below.One type isknn(l)>knn(l+m1)>knn(N-1)>knn(N-1+m2), which is the scenario of most of the cases belonging to and matching our prediction that knn(k) decreases when degree k is increasing.The 2nd type isknn(l)<knn(l+m1),knn(N-1)<knn(N-1+m2), but knn(l)≫knn(N-1+m2), which is different from what we predicted. However, the overall trend is that knn(k) decreases when degree k is increasing while nodes with degree l+m1 and N-1+m2 have minor positive variation.


## 4. The Ideal Network Connecting Centers of Two Sub-Networks

For the 2nd connecting method, that is, connecting sub-networks I and II through connectingm1 centers of I to m2 centers of II, we can also let 0<m1≤m2≤l and m1=αl, m2=βl where α shows the proportion of connecting nodes in centers of sub-network I, β shows the proportion of connecting nodes in centers of sub-network I, α,β∈(0,1], and α≤β.Similarly as the first situation, all nodes of the network can be divided into four types based on the degree property, which are nodes with degreel, N-1, N-1+m1, N-1+m2. And then we can obtain matrix {p(k′/k)} as follows:(4.1)(02l-m2-m12lm22lm12l(2l-m2-m1)(N-l)Δ1(l-m1)(l-m1-1)+(l-m2)(l-m2-1)2Δ1(l-m2)m2Δ1(l-m1)m1Δ1N-lΔ2l-m2Δ2m2-12Δ2m1Δ2N-lΔ3l-m1Δ3m2Δ3m1-12Δ3),
where(4.2)Δ1=(l-m2-m1)(N-l)+(N-1)l-12m1(m1-1)-12m2(m2-1),Δ2=N-12m2-12+m1,Δ3=N-12m1-12+m2.Subsequently we can derive the expressions of avrage neighbor connectivity to nodes with the degreel, N-1, N-1+m1, N-1+m2, respectively, which are listed follows:(4.3)knn(l)=(N-1)+m1m2l,knn(N-1)=l(2l-m2-m1)(N-l)Δ1+(N-1)(l-m1)(l-m1-1)+(l-m2)(l-m2-1)2Δ1+(N-1+m1)(l-m2)m2Δ1+(N-1+m2)(l-m1)m1Δ1,knn(N-1+m1)=lN-lΔ2+(N-1)l-m2Δ2+(N-1+m1)m2-12Δ2+(N-1+m2)m1Δ2,knn(N-1+m2)=lN-lΔ3+(N-1)l-m1Δ3+(N-1+m2)m1-12Δ3+(N-1+m1)m2Δ3.Figure3 is a three-dimensional graph of relationship between r and α, β under the assumption that N=1000, l=20. The trend how r varies with α, β can easily be observed.Figure 3
Relation betweenr and α,β when N=1000, l=20(x=α,y=β).Assortativity coefficientr varies between −0.9810 and −0.9597 across α, β in the ideal network connecting centers of sub-network I and sub-network II. the range of the variation is very limited. It appears that this network is disassortative. In most cases r is slightly greater than that of single multi-center network (r=-0.9810). It shows that this network is relatively less disassortative than the single multi-center network, which correlates to the connecting method. Connecting centers of sub-network I and sub-network II increases the average degree level of centers in sub-networks while the degree of non-center nodes does not change. The whole network is constructed by connecting a few nodes with high degree to a lot of nodes with low degree. Therefore, the network is disassortative.Under the same assumption thatN=1000, l=20, Figure 4 illustrates the relationship between knn(k) and degree k in the ideal network with this connecting method.Figure 4
knn(N-1)<knn(N-1+m1)<knn(N-1+m2), but knn(l)≫knn(N-1+m2).In the ideal network connecting centers of sub-network I and sub-network II, nodes with the degreel, N-1, N-1+m1, N-1+m2 have the average neighbor connectivity knn(l), knn(N-1), knn(N-1+m1), knn(N-1+m2), respectively. The relationship between the average neighbor connectivity can be described as followsknn(N-1)<knn(N-1+m1)<knn(N-1+m2), but
(4.4)knn(l)≫knn(N-1+m2).The above expression does not correlate to our prediction thatknn(k) should monotonically decrease with degree k. However, values of knn(N-1), knn(N-1+m1), knn(N-1+m2) are much smaller than knn(l), and the value differences among these three are also much smaller than knn(l). Even though the nodes with degree N-1+m1 and N-1+m2 do not agree with the disassortativity, the overall trend is that knn(k) decreases as degree k is increasing.


## 5. The Ideal Network Connecting NonCenter Nodes of Two Sub-Networks

To connect sub-networks I and II in the third situation means to connectm1 non-center nodes of I to m2 non-center nodes of II. We can also let 0<m1<m2<N-l and m1=α(N-l), m2=β(N-l) where α shows the proportion of connecting nodes in non-center nodes of sub-network I, β shows the proportion of connecting nodes in non-center nodes of sub-network II, α,β∈(0,1] and α≤β.Similar to the first and second situations, all nodes of the network can be divided into four types based on the degree property, which are nodes with degreel, l+m1, l+m2, N-1. And then we can obtain matrix {p(k′/k)} as follows:(5.1)(000100m1m1+llm1+l0m2m2+l0lm2+l2N-2l-m1-m22N-l-1m22N-l-1m12N-l-1l-12N-l-1)Subsequently we can derive the expressions of average neighbor connectivity to nodes with the degreel, l+m1, l+m2, N-1, respectively, which can be listed as follows:(5.2)knn(l)=N-1,knn(l+m1)=(l+m2)m1m1+l+(N-1)lm1+l,knn(l+m2)=(l+m1)m2m2+l+(N-1)lm2+l,knn(N-1)=l2N-2l-m1-m22N-l-1+(l+m1)m22N-l-1+(l+m2)m12N-l-1+(N-1)l-12N-l-1.Figure5 is a three-dimensional graph of the relationship between r and α, β under the assumption that N=1000, l=20. The trend how r varies along with α, β can easily be observed.Figure 5
Relation betweenr and α,β when N=1000, l=20(x=α,y=β).Assortativity coefficientr varies in wide range across α, β in the ideal network connecting non-center nodes of sub-network I and sub-network II (−0.9810~0.7122). The values of r are mostly negative. It is obvious that the network is disassortative with a few exceptions, which correlates to the connecting method of this network.After connecting non-center nodes of sub-network I and sub-network II, the average degree level of non-center nodes in sub-networks increases. Even when a large number of non-center nodes with low degree (as long as the quantity is belowN-l) become connecting nodes, the degree of this kind of nodes increases greatly such that they become nodes with high degree. The whole network is constructed by connecting nodes with high degree. Therefore, the network is assortative, even though its two sub-networks are disassortative. And it is obvious that assortativity shows up when values of α, β are both close to 1.Similarly, under the assumption thatN=1000, l=20, Figure 6 shows the relationship between knn(k) and degree k in the ideal network with this connecting method.(a)knn(l)>knn(l+m1)>knn(l+m2)>knn(N-1). (b) knn(l)<knn(l+m1)<knn(l+m2)<knn(N-1).
(a)(b)In the ideal network of connecting non-center nodes of sub-network I and sub-network II, nodes with the degreel, l+m1, l+m2, N-1 have the average neighbor connectivity knn(l), knn(l+m1), knn(l+m2), knn(N-1), respectively. The relationship of average neighbor connectivity can be expressed as:(5.3)knn(l)>knn(l+m1)>knn(l+m2)>knn(N-1).Butknn(l+m1), knn(l+m2) and knn(N-1) increase as α, β are increasing, which are gradually close to knn(l) then finally exceed knn(l) slightly as shown in Figure 6(b). The network owns assortative property in these few examples, which is different from what we have predicted. This means that knn(k) increases as degree k is increasing in these examples.


## 6. Discussions

This paper has studied three ways of connecting two multi-center sub-networks. Based on the analysis of the three scenarios, it can be summarized that disassortative properties can be changed by changing the connecting ways between communities. For a network consisting of two disassortative multi-center sub-networks, connecting hub and nodes with lower degree can still generate a disassortative network, but the disassortativity is weakened; connecting hubs can maintain the disassortativity to a great extent; connecting nodes with lower degree can even change disassortativity to assortativity.Based on the analytical study of the impact of interconnection on disassortativity, it can be concluded that two communities (taking a network with disassortativity as an example) with basically the same structure form a new larger network. Different connecting ways between two communities lead to different levels of disassortativity of the whole network. Connecting nodes with mixed high and low degrees can still form disassortative network with weakened disassortativity; connecting nodes with high degree can maintain the disassortativity; connecting nodes with low degree can even change disassortativity to assortativity when the number of connections reaches certain amount.We also conclude that the assortativity coefficientr can be used to evaluate assortativity or disassortativity of networks in whole. If the degree-degree correlation knn(k) is also used to evaluate assortativity or disassortativity, using its overall trend is sufficient and the curve does not have to be monotonic.In addition, once going deep into the analytical conclusion above, we find that this assortativity/disassortativity is just a parameter and cannot describe a network by itself. This is apparent as a complex network is a high-dimensional object, it is impossible to use a single parameter—a one—dimensional line, to fully describe it. Under certain circumstance, when one property is dominant for a certain application, one can neglect the other properties, and then it becomes a 1D problem, as in this paper.



---

*Source: 891267-2010-12-01.xml*