Abstract
Many social and biological networks consist of communities-groups of nodes within which connections are dense, but between which connections are sparser. Recently, there has been considerable interest in designing algorithms for detecting community structures in real-world complex networks. In this paper, we propose an evolving network model which exhibits community structure. The network model is based on the inner-community preferential attachment and inter-community preferential attachment mechanisms. The degree distributions of this network model are analysed based on a meanfield method. Theoretical results and numerical simulations indicate that this network model has community structure and scale-free properties.
Introduction
Complex networks are currently being studied across many fields of science and engineering [1] , stimulated by the fact that many systems in nature can be described by models of complex networks. A complex network is a large set of interconnected nodes, in which a node is a fundamental unit usually with specific dynamical or information content. Examples include the Internet, which is a complex network of routers and computers connected by various physical or wireless links; the World Wide Web, which is an enormous virtual network of web sites connected by hyperlinks; and various communication networks, food webs, biological neural networks, electrical power grids, social and economic relations, coauthorship and citation networks of scientists, cellular and metabolic networks, etc. The ubiquity of various real and artificial networks naturally motivates the current intensive study of complex networks, on both theoretical and application levels.
Many properties of complex networks have currently been reported in the literature. Notably, it is found that many complex networks show the small-world property [2] , which implies that a network has a high degree of clustering as in some regular network and a small average distance between nodes as in a random network. Another significant recent discovery is the observation that many large-scale complex networks are scale free. This means that the degree distributions of these complex networks follow a power-law form P (k) ∼ k −γ for large network size, where P (k) is the probability that a node in the network is connected to k other nodes and γ is a positive real number determined by the given network. Since power laws are free of characteristic scale, such networks are called 'scale-free networks' [3] . The scale-free nature of many real-world networks can be generated by a mechanism of growing with preferential attachment [3] .
Communities are defined as collections of nodes within which connections are dense, but between which connections are sparser. There are many real-world networks which exhibit community structure, and community structures are supposed to play an important role in many real networks. For example, communities in a citation network might represent related papers on a single topic [4] ; communities on the web might represent pages on related topics [5] ; communities in a biochemical network or neuronal system might correspond to functional units of some kinds [6, 7] ; and communities also play an important role in information networks [8] . There have been several investigations into designing algorithms for detecting community structure in large-scale complex networks [9, 10] . To study the effects of community structure on network properties and dynamics, the modelling of real networks with community structure is very important. However, most of the existing evolving network models do not take the community structure into account. In [11] , a networked seceder model was proposed to illustrate group formation in social networks. In [12] , a bipartite growing network model for social community with group structures was proposed. In [13] , a social network model based on social distance attachment was proposed, which can exhibit community structure. In [14] , the authors proposed a growing network model with community structure. However, there is the possibility within the network model that a node belongs to a community but has no connections with nodes in this community but has connections with nodes in other communities, which is unacceptable.
In this paper, we propose an evolving network model with community structure based on the inner-community preferential attachment and inter-community preferential attachment mechanics. We use a mean-field method to analyse the degree distributions of this network model. Numerical simulations are also performed to investigate the properties of this network model. Some more realistic generalizations and extensions are also discussed in section 4.
Network model
In this section, we describe the growing mechanics of the proposed network model. For simplicity, we consider only undirected network models in this paper. We assume that there is a total of M (M 2) communities in the network. The proposed model is defined by the following scheme. so that there is a link between each community. The nodes to which the inter-community links connect are selected randomly in each community. For example, figure 1 shows an initial network with M = 3 and m 0 = 3.
Step 2: growth
At each time step, a new node is added to a randomly selected community. The new node will be connected to m (1 m m 0 ) nodes in the same community through m inner-community links (defined as the links that connect nodes in the same community), and with probability α connected to n (1 n m) nodes (none with probability 1 − α) in the other M − 1 communities through inter-community links (defined as the links that connect nodes among different communities).
Step 3: preferential attachments (a) Inner-community preferential attachment. When choosing nodes in the same community (we denote it as the j th community) to which the new node connects through innercommunity links, we assume that the probability that a new node will be connected to node i in community j depends on the inner-degree s ij (defined as the number of inner-links connected to node i) of that node, such that
(b) Inter-community preferential attachment. When choosing the nodes in other communities to which the new node connects through inter-community links, we assume that the probability that a new node will be connected to node i in community k (k = j) depends on the inter-degree l ik (defined as the number of inter-links connected to the node), such that
The motivation for using the inner-community preferential attachment mechanics is the same as that in many other growing network models. There also exist inter-community preferential attachment phenomena in some real networks with community structure. For example, in scientific collaboration networks, a multidisciplinary researcher is more likely to be willing to study other unknown fields to him/her, and has stronger desire to collaborate with researchers in other fields than other single-topic researchers. In friendship networks, an individual with many inter-community links is more likely to make friends with different kinds of people, and has higher probability of making new friends with people in other communities than other people with less inter-community links. These are all inter-community preferential attachment phenomena.
After t time steps, this scheme generates a network with Mm 0 + t nodes, and [Mm 0 (m 0 − 1) + M(M − 1)]/2 + mt + integer(αnt) links in the sense of mathematical expectation. The parameters α and n control the ratio between inter-and inner-community links.
We performed a numerical simulation with a total of N = 90 nodes, m 0 = m = 3, n = 1 and the probability α = 0.1, that is, at each time step, we connect a new node with three nodes in a selected community and with probability α = 0.1 connect it to a node in another community. For the purposes of clarity, the generated network is shown in figure 2 , in which the nodes in each community are randomly placed. As we can see, the network generated by the proposed scheme exhibits community structure. A detailed study of the properties of this network model will be presented in the next section.
Network properties
In this section, firstly we analytically calculate the degree distribution P (k), which is defined as the probability that a randomly selected node has degree k (a node has k connections), and then we numerically study some properties of this network model.
We use a mean-field method [15] to analyse the scaling property of the network model. Firstly we analyse the inner-degree distribution, and then extend the results to that of the interdegree and the total degree (defined as the sum of the inner-degree and inter-degree). Similar to [15] 
The solution of this equation, with the initial condition that node i in community j was added to the system at time t i with connectivity s ij ( 
Using (5), the probability that a vertex has a connectivity s ij (t) smaller than k can be written as
Assuming that we add the nodes (including the initial nodes) at equal time intervals to the network, the probability density of t i is
By substituting (7) into (6), we have
The probability density for P (k) can be obtained using
predicting that the inner-degree distribution obeys a power-law distribution P (k) ∼ k −γ with γ = 3 independent of M and m.
Similarly,
in which
in the sense of mathematical expectation. If α = 0, then no inter-community links are added in the evolution of the network, and the total number of inter-community links is always
. If α = 0, then the solution of this equation, with the initial condition that node i in community k was added to the network at time t j with inter-community connectivity l ik (t j ) = αn in the sense of mathematical expectation, is l ik (t) = αn t + β t j + β 0.5 (12) with β =
. If α is not so small, such that 2
] for large t (usually, this is the case), then
The solution of this equation, with the initial condition that node i in community k was added to the network at time t j with inter-community connectivity l ik (t j ) = αn in the sense of mathematical expectation, is
Similar to the above analysis of the inner-degree distribution, the inter-degree distribution P (k) can be written as
predicting that the inter-degree distribution also obeys a power-law distribution
with γ = 3 independent of M, α and n. In this case, the total degree of node i in community j is
It is easy to show that the total degree distribution is
which indicates that the total degree also obeys a power-law distribution
Because αn < m (usually αn m), from (5) and (14) (or (12)) we know that the interdegrees of network nodes are smaller than the inner-degrees of network nodes in the sense of statistics. So, networks generated by this model will have community structure.
Next, we numerically study the properties of the network model. We consider a network generated by the proposed scheme with M = 3, m 0 = 3, m = 3, α = 0.3, n = 1 and N = 3000. In figures 3-5, the slopes of the lines were obtained by cumulative distributions of 10 runs. The inner-degree distribution of this network is shown in figure 3 . As we can see, the inner-degree obeys a power-law distribution P (k) ∼ k −γ with γ ≈ 3 (the slope of the line is −3). The inter-degree distribution is shown in figure 4 , and the inner-degree obeys a power-law distribution P (k) ∼ k −γ with γ ≈ 2.9 (the slope of the line is −2.9). The total degree distribution is shown in figure 5 , and we observe that the total degree also obeys a power-law distribution P (k) ∼ k −γ with γ ≈ 3. So, all these three distributions are of power-law type, indicating that the generated network is a scale-free network, and these distributions verify the above analytical results. In figure 6 we plot the time evolution of the total degree of two nodes, in which one is an initial node and the other one is added to the network at t = 60. This is in good agreement with (16) .
We also calculated the diameter D, the average path length l and the clustering coefficient C for this network. The detailed definitions of these parameters can be found in [1] . The values of these parameters are D = 7, l = 4.0274 and C = 0.0270, respectively. So the network has small average path length and relatively large clustering coefficient (compared to a random graph). Figure 6 . The time evolution of the degree of two nodes, one is an initial node (the upper one) and the other one was added to the network at t = 60 (lower one). As can be seen, the time evolution of the degrees is well approximated by a straight line with gradient 0.5.
Conclusions and remarks
In this paper we proposed an evolving network model with community structure. We have theoretically analysed the scaling properties of the network by using a mean-field approach. The analytical and numerical results indicate that the network can produce community structure, and the inner-degree, inter-degree and total degree all obey power-law distributions, so the network has scale-free properties. The network also has small average path length and relatively large clustering coefficient (compared to a random graph). Note that in [16] the authors proposed a growing network model of two coupled networks-this idea is a little similar to that in the present paper, but the authors did not consider community structure.
To make our model more understandable and to avoid unnecessarily complicated notations, we made some simplifications in our model. Some more realistic cases and extensions can be considered with minor modification of our model, for example:
(1) We did not consider the formation of new communities during the evolution of the network model. In some real-world networks, some new communities may appear during the evolution. With minor modification, our model could allow from time to time the introduction of new communities: if a node i is the first of a new community, one could only set links between i and the old communities at the time step of its introduction, and follow the same evolving rules in the proceeding time steps as defined in section 2. It is easy to show that, with this modification, the main results will not change. (2) In the preferential attachment mechanism, if a node i is not connected to a node j (in the same community or different communities) at the beginning of its introduction, it will never be. In considering the resulting networks, this is of no problem, but in considering the evolution process, it is somewhat unrealistic. We can overcome this problem as follows: in each time step, besides the steps mentioned in section 2, with probability β, an existing node is selected, and we perform the same inner-and inter-community attachments of this node to all the other existing nodes that have no links with it. This will surely not change the community structure of the network model.
Future extensions of this work include considering other kinds of inner-and inter-linking mechanisms other than preferential attachment, such as preferential linking [17] and distance preference [18] . Future extensions also include the modelling of directed and weighted network models with community structure [19] because many real-world networks with community structures are directed and/or weighted [20] . Based on this network model, we can study the effects of community structure on network dynamics, such as stability, synchronization, disease and rumour spreading and robustness. We can also introduce different types of dynamical node models in different communities to study the dynamical behaviour of some real networks, for example, biochemical networks and brain networks.

{'paper_id': '17712212', 'title': 'An evolving network model with community structure', 's2_url': 'https://api.semanticscholar.org/CorpusID:17712212', 'source': 'S2ORC'}