Online Community Detection for Large Complex Networks

1 Introduction

Complex networks describe a wide range of systems in nature and society [Barrat et al., 2004]. Frequently cited examples include the Internet, a network of routers and computers connected by physical links, and the citation network, a network of papers linked by citations. To understand the formation, evolution, and function of complex networks, it is crucial to investigate their internal structure, not only for uncovering the relations between internal structure and functions in complex networks, but also for practical applications in many disciplines such as biology and sociology [Ratti et al., 2010; Szell et al., 2012].

The problem of community detection is one of the outstanding issues in the study of network structure. A wide variety of community detection methods have been developed to serve different scientific needs. For example, [Ahn et al., 2010] reinvent communities as groups of links rather than nodes and show that this unorthodox approach successfully reconciles the antagonistic organizing principles of overlapping communities and hierarchy. [Ziv et al., 2005] propose a principled information-theoretic algorithm for community detection. However, when processing large complex networks, most existing community detection methods become impractical owing to the requirement that the whole network structure be available at each step of the method. For this reason, there has been a strong interest for online community detection method which make it possible to detect community without accessing the whole network structure at each step.

∗Author for correspondence

In this paper, we consider the generative mechanism of complex networks which has mainly not been considered in past studies and propose an online community detection method. Our method has O(m) time complexity and O(nk) space complexity. The results of applying our method and some other feasible methods to real-world network datasets suggest that our method is scalable and competitive in performance.

2 RelatedWork

Traditional methods of community detection, such as spectral bisection, the Kernighan-Lin algorithm and hierarchical clustering based on similarity measures are not ideal for the types of real-world network datasets with which current research is concerned [Newman, 2004b]. Modularity is a recently introduced quality measure for community detection. It was first proposed in [Newman, 2004b]. [Good et al., 2010] describe the performance of modularity maximization in practical contexts and present a broad characterization of its performance in such situations. However, [Fortunato and Barthelemy, 2007] find that modularity optimization may fail to identify communities smaller than a scale which depends on the total size of the network and on the degree of interconnectedness of the communities. A check of the communities obtained through modularity optimization is thus necessary.

Modularity can be generalized in a principled fashion to incorporate the information contained in edge such as direction and weightiness. [Leicht and Newman, 2008] consider the problemof finding communities in directed networks. [Newman, 2004a] point out that weighted networks can in many cases be analyzed using a simple mapping from a weighted network to an unweighted multigraph. [Lancichinetti and Fortunato, 2009] generate directed and weighted networks with built-in community structure and show how modularity optimization performs on their benchmark.

A wide variety of modularity optimization methods have been developed [Leskovec et al., 2010]. For example, [Clauset et al., 2004] present a hierarchical agglomeration algorithm for detecting community. [Newman, 2006] show that the modularity can be expressed in terms of the eigenvectors of a characteristic matrix for the network and that this expression leads to a spectral algorithm for community detection. [Chen et al., 2011] introduce a game-theoretic framework to address the community detection problem based on the social networks structure. [Li and Schuurmans, 2011] propose an iterative rounding strategy for identifying the communities that is coupled with a fast constrained power method that sequentially achieves tighter spectral relaxations. [Chan and Yeung, 2011] propose a convex relaxation scheme to give an iterative algorithm which solves the general kpartition problem. [Wu et al., 2011] first projects node coordinates to the unit sphere and then applies the classic k-means to find communities. [Chen et al., 2009] present a new community mining measure, max-min modularity, which considers both connected pairs and criteria defined by domain experts in finding communities, and then specify a hierarchical clustering algorithm to detect communities in networks. A recent comparative analysis of community detection algorithms is in [Lancichinetti and Fortunato, 2009].

3 Online Community DetectionMethod

3.1 Preliminaries

A network G = {V,E} is a set of n nodes V = {v1, v2, . . . , vn} connected by a set of m edges E = {eij = {vi, vj}}. The network considered here is undirected, unweighted and without self-loops or isolated node. Let P = {C1, . . . ,CK} denote a partition of V , it is a division of V into K non-overlapping and non-empty communities Ck that cover all of V . As a performance measure for the quality of the partition, modularity was first proposed in [Newman, 2004b] and can be expressed as

where edg(Ck) = |{eij|vi ∈ Ck and vj ∈ Ck}| is the number of intra-community edges within Ck and deg(Ck) is the degree of Ck defined as deg(Ck) = ∑vi∈Ck deg(vi) where deg(vi) is the degree of node vi. Hence community detection can be formulated as an optimization problem

and [Brandes et al., 2008] prove the conjectured hardness of this problem both in the general case and with the restriction to number of partitions K.

3.2 Analysis of network expansion

Unlike most previous approaches, we consider networks as a result of expanding. It is growing by the addition of new edges. Given an existing network Gt-1 = {Vt-1,Et-1}, there are three cases for a new edge et = {vi, vj} to be added in Gt-1, namely, (a)link a new node to an existing node, {vi, vj} ∩ Vt-1 = {vi} or {vi, vj} ∩ Vt-1 = {vj}; (b)link two existing nodes, {vi, vj} ⊆ Vt-1; (c)link two new nodes, {vi, vj} ∩ Vt-1 = ∅(See Fig. 1).

Correspondingly, we do modularity optimization in a incremental way. For initial network G0 = ∅, it is clearly that the best partition P is an empty set too. For subsequent networks Gt, t = 1, 2, . . ., we derive our algorithm under those three cases separately as follow.

Case (a): link a new node to an existing node. Without loss of generality, we assume vi is the existing node and vj is the new node. It is easy to prove that a partition with maximum modularity has no community that consists of a single node with degree one. It seems that we should assign vj to an existing community. However, this greedy approach will almost certainly lead to a local maximum. In worst case, all nodes are in a same community and result in zero modularity. Hence a split mechanism is necessary.

Let us recall the generative mechanism of complex networks. The first widely accepted model for the observed stationary scale-free distributions of complex networks was proposed by [Barab´asi and Albert, 1999] and its importance is recognized by academia [Newman, 2003; Boccaletti et al., 2006]. It is based on two generic mechanisms: (a) networks expand continuously by the addition of new nodes; (b) new nodes attach preferentially to communities that are already well connected. Specifically, a new node vj will attach an existing node vi with probability p(vi) in proportion to the degree of node vi.

In other words, it is abnormal to observe a new node attaching an existing node with few edges and this phenomenon may indicate the emergence of a new community. This inspire us to split the new node to a new community with probability psplit that decreases with increases in the degree of the existing node. And the limit of psplit, as the degree of the existing node approaches infinite, should be zero. We choose psplit inversely proportional to the degree of the existing node.

Here we use deg(vi)+1 instead of deg(vi) to avoid deterministic split when deg(vi) = 1. Fig. 2 depict our split mechanism. When a new node attaches to an existing node with degree two, it join the same community of the existing node; when another new node attaches to the previous new node with degree one, it split to a new community.

For a complete review of the statistical mechanics of network topology and dynamics of complex networks, one can refer to [Albert and Barab´asi, 2002]. And [Mitzenmacher, 2004] briefly survey some other generative models that lead to scale-free distributions.

Case (b): link two existing nodes. Existing nodes may belong to a same community or not(See Fig. 3). If both nodes belong to a same community, the new edge just increase the number of intra-community edges in the community so we do nothing. If they belong to different communities, we evaluate ∆q(vi, vj), which is defined as modularity gain for node vi moving from it's community Ck(i) to node vj's community Ck(j), and ∆q(vi, vj)'s counterpart ∆q(vj, vi). If either of them larger than zero, we move one node according to maximum modularity gain principle.

Notice that ∆q(vi, vj) can be calculated in constant time through follow equation

where deg(vi,Ck) = |{eij|vj ∈ Ck}| is number of edges from the node vi to community Ck and Ck(i) is the community which the node vi belongs to.

We can improve modularity via other types of adjustments. For example, the modularity gain of merging two communities Ck(i) and Ck(j) is

where deg(Ck(i),Ck(j)) is number of edges between community Ck(i) and community Ck(j). Sometimes ∆q(Ck(i), Ck(j)) can be positive and significantly larger than ∆q(vj, vi) and ∆q(vi, vj). However, merging two communities may cause that subsequent optimazitions suffer from overlarge community size. For the sake of simplicity, we do not take those complex adjustments.

Case (c): link two new nodes. As a partition of maximum modularity does not include disconnected communities, those two nodes should not join any existing communities but form a new community themselves.

3.3 The proposed algorithm

Taken together, our method take a sequence of edges as input and do modularity optimization incrementally. If only one node of current edge belongs to the existing network, we split another node to a new community with probability inversely proportional to the degree of the existing node; If both nodes of current edge belong to the existing network but they belong to different communities, we move one node according to maximum modularity gain principle; If neither node of current edge belongs to the existing network, we just assign them to a new community. Obviously, our online community detection algorithm has O(m) time complexity. And the space complexity is O(nk) because we need to store deg(vi,Ck) for calculating modularity gain in constant time. The algorithm is summarized in Algorithm 1.

4 Experiments

In this section, we present experimental results of our online community detection method and compare it with some other methods. For simplicity, we use OL to refer to our method, CNM to refer to an agglomerative method [Clauset et al., 2004] and Eig to refer to the eigenvector-based method [Newman, 2006].

We use six real-world network datasets from Stanford Large Network Dataset Collection 1 , which commonly used by other researchers for community detection, their edge sizes varying from 93,439 to 1,992,636(See Table 1). These datasets are

• ca-CondMat: Collaboration network of Arxiv Condensed Matter [Leskovec et al., 2007];
• ca-HepPh: Collaboration network of Arxiv High Energy Physics [Leskovec et al., 2007];
• ca-AstroPh: Collaboration network of Arxiv Astro Physics [Leskovec et al., 2007];
• cit-HepTh: Arxiv High Energy Physics paper citation network [Leskovec et al., 2005];
• cit-HepPh: Arxiv High Energy Physics paper citation network [Leskovec et al., 2007]
• web-Stanford: Web graph of Stanford.edu [Leskovec et al., 2009].

The edges should be processed in order of creation. However, the datasets do not have timestamps on the edges. We process the edges in order of their appearance in the raw dataset file.

1 http://snap.stanford.edu/data/

We use C# to implement our algorithm 2 . For comparison, we employ implementation of CNM algorithm and Eig algorithm in igraph package 3 in R software 4 . Both CNM algorithm and Eig algorithm are written in C language. We carry out experiments on a Windows based Genuine Intel(R) CPU i3 @ 3.20GHz machine with 4.00GB memory.

Maximum and average modularity and variance of modularity over 10 runs by OL as well as modularity over 10 runs by Eig and CNM are reported in Table 2. We can see that OL outperforms Eig consistently for all six datasets and outperforms CNM except the last dataset, and the gap between OL and CNM in the last dataset is less than 0.02. The variance is low, so we need not run multiple times.

Average running time(in seconds) over 10 runs by OL, Eig and CNM are reported in Table 3 and Fig. 4. OL also has significantly advantage in terms of running time. It is linear in edge size as we expected. For networks with two millions of edges, it can give result in six seconds which is six hundred times faster than CNM.

To evaluate the convergence speed of OL, we plot the average temporal modularity over 10 runs by OL(See Fig. 5). We can see that OL can give a acceptable modularity immediately after process start and the modularity becomes stable in early stage for all six datasets.

5 Conclusion

In this paper we have examined the problem of detecting community in large complex networks, which is formulated as an optimization problem in which one searches for the maximum of the quantity known as modularity over possible partition of a network. We have considered the generative mechanism of complex networks and presented a new method which allows us to perform online modularity maximization. The method has been applied to a variety of realworld network datasets and our experiments give very encouraging results. Not only is the proposed method scalable in terms of both time and space complexity, but it also gives competitive performances. Our future research will consider the use of quality measures other than modularity for solving the community detection problem under an online optimization framework, as well as apply the method to directed and weighted complex networks.

2 Our C# implementation can be downloaded from http://www.cs.zju.edu.cn/people/gpan/

3 http://igraph.sourceforge.net/

4 http://www.r-project.org/

Acknowledgments

The authors want to thank anonymous reviewers for helpful comments. This work was supported by National Key Basic Research Program of China(2013CB329504) and Qianjiang Talent Program of Zhejiang(2011R10078).