TITLE:
The Effects of Centrality Ordering in Label Propagation for Community Detection
AUTHORS:
Brian Dickinson, Wei Hu
KEYWORDS:
Community Detection, Label Propagation, Centrality, Overlapping Community Detection
JOURNAL NAME:
Social Networking,
Vol.4 No.4,
October
9,
2015
ABSTRACT: In many cases randomness in community detection algorithms has been avoided due to issues
with stability. Indeed replacing random ordering with centrality rankings has improved the performance
of some techniques such as Label Propagation Algorithms. This study evaluates the effects
of such orderings on the Speaker-listener Label Propagation Algorithm or SLPA, a modification
of LPA which has already been stabilized through alternate means. This study demonstrates
that in cases where stability has been achieved without eliminating randomness, the result of removing
random ordering is over fitting and bias. The results of testing seven various measures of
centrality in conjunction with SLPA across five social network graphs indicate that while certain
measures outperform random orderings on certain graphs, random orderings have the highest
overall accuracy. This is particularly true when strict orderings are used in each run. These results
indicate that the more evenly distributed solution space which results from complete random ordering
is more valuable than the more targeted search that results from centrality orderings.