Fast community detection based on sector edge aggregation metric model in hyperbolic space

Zuxi Wang, Qingguang Li, Wei Xiong, Fengdong Jin and Yao Wu

Physica A: Statistical Mechanics and its Applications, 2016, vol. 452, issue C, 178-191

Abstract: By studying the edge aggregation characteristic of nodes in hyperbolic space, Sector Edge Aggregation Metric (SEAM) model is proposed and theoretically proved in this paper. In hyperbolic disk SEAM model determines the minimum angular range of a sector which possesses the maximal edge aggregation of nodes. The set of nodes within such sector has dense internal links, which corresponds with the characteristic of community structure. Based on SEAM model, we propose a fast community detection algorithm called Greedy Optimization Modularity Algorithm (GOMA) which employs greedy optimization strategy and hyperbolic coordinates. GOMA firstly divides initial communities according to the quantitative results of sector edge aggregation given by SEAM and the nodes’ hyperbolic coordinates, then based on greedy optimization strategy, only merges the two angular neighboring communities in hyperbolic disk to optimize the network modularity function, and consequently obtains high-quality community detection. The strategies of initial community partition and merger in hyperbolic space greatly improve the speed of searching the most optimal modularity. Experimental results indicate that GOMA is able to detect out high-quality community structure in synthetic and real networks, and performs better when applied to the large-scale and dense networks with strong clustering.

Keywords: Edge aggregation metric; Community detection; Hyperbolic space; Complex network (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378437116000595
Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:phsmap:v:452:y:2016:i:c:p:178-191

DOI: 10.1016/j.physa.2016.01.020

Access Statistics for this article

Physica A: Statistical Mechanics and its Applications is currently edited by K. A. Dawson, J. O. Indekeu, H.E. Stanley and C. Tsallis

More articles in Physica A: Statistical Mechanics and its Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().