Generalized Modularity for Community Detection
Detecting the underlying community structure of networks is an important problem in complex network analysis. Modularity is a well-known quality function introduced by Newman, that measures how vertices in a community share more edges than what would be e
- PDF / 1,272,919 Bytes
- 16 Pages / 439.37 x 666.142 pts Page_size
- 54 Downloads / 221 Views
3
Amirkabir University of Technology, Tehran, Iran [email protected], [email protected] 2 Iran University of Science and Technology, Tehran, Iran [email protected] NICTA, Victoria Laboratory, Department of Computing and Information Systems, University of Melbourne, Melbourne, Victoria {baileyj,pstuckey}@unimelb.edu.au
Abstract. Detecting the underlying community structure of networks is an important problem in complex network analysis. Modularity is a well-known quality function introduced by Newman, that measures how vertices in a community share more edges than what would be expected in a randomized network. However, this limited view on vertex similarity leads to limits in what can be resolved by modularity. To overcome these limitations, we propose a generalized modularity measure called GM which has a more sophisticated interpretation of vertex similarity. In particular, GM also takes into account the number of longer paths between vertices, compared to what would be expected in a randomized network. We also introduce a unified version of GM which detects communities of unipartite and (near-)bipartite networks without knowing the structure type in advance. Experiments on different synthetic and real data sets, demonstrate GM performs strongly in comparison to several existing approaches, particularly for small-world networks. Keywords: Community detection · Modularity modularity · Vertex similarity · Resolution limit
1
·
Generalized
Introduction
As many real-world systems can be represented by networks, much research has focused on analysing networks and finding underlying useful structural patterns. Examples include social and biological networks [1,2], in which vertices represent individuals or proteins and edges represent communications or interactions. Among complex network analysis approaches, community detection is an important task which aims to find groups of vertices which could share common properties and/or have similar roles within the network [3]. This might reveal friendship communities in a social network or an unexpected hard-to-predict community structure in a biological dataset. c Springer International Publishing Switzerland 2015 A. Appice et al. (Eds.): ECML PKDD 2015, Part II, LNAI 9285, pp. 655–670, 2015. DOI: 10.1007/978-3-319-23525-7 40
656
M. Ganji et al.
Two important network structures covered in the literature are unipartite and bipartite networks. In unipartite networks like social networks [1], the assumption is connections within communities are dense and connections between communities are sparse. However, some real networks are bipartite which means they can be partitioned into two clusters such that no two vertices within the same cluster are adjacent [4]. People attending events [5] is one example of a bipartite network. In addition, there are some real networks with near-bipartite properties. In these networks, there are some connections inside the two communities but they are fewer than between-community connections. Networks of sexual relationship
Data Loading...
