An Optimized Approach for Community Detection and Ranking
Document Type
Article
Publication Date
1-1-2016
Publication Title
Journal of Big Data
Volume
3
Issue
1
Abstract
Community structures and relation patterns, and ranking them for social networks provide us with great knowledge about network. Such knowledge can be utilized for target marketing or grouping similar, yet distinct, nodes. The ever-growing variety of social networks necessitates detection of minute and scattered communities, which are important problems across different research fields including biology, social studies, physics, etc. Existing community detection algorithms such as fast and folding or modularity based are either incapable of finding graph anomalies or too slow and impractical for large graphs. The main contributions of this work are twofold: (i) we optimize the Attractor algorithm, speeding it up by a factor depending on complexity of the graph; i.e. the more complex a social graph is, the better result the algorithm will achieve, and (ii) we propose a community ranker algorithm for the first time. The former is achieved by amalgamating loops and incorporating breadth-first search (BFS) algorithm for edge alignments and to fill in the missing cache, preserving a constant of time equal to the number of edges in the graph. For the latter, we make the first attempt to enumerate how influential each community is in a given graph, ranking them based on their normalized impact factor. © 2016, The Author(s).
Keywords
Betweenness; Breadth-first search; Community strength; Complex networks; Jaccard index; Modularity
Language
English
Repository Citation
Pirouz, M.,
Zhan, J.,
Tayeb, S.
(2016).
An Optimized Approach for Community Detection and Ranking.
Journal of Big Data, 3(1),
http://dx.doi.org/10.1186/s40537-016-0058-z