Most existing methods use only network topology information, which neglect much other important information such as the network background information which could be useful to uncover the network communities. In this paper, we proposed a fast semi-supervised algorithm to uncover the fuzzy network communities using label propagation technology, which incorporating the prior information to facilitate the community detection process. Specially, we know the true community membership of a certain percentage nodes in advance. Firstly, the node graph is transformed to line graph, and the weight of line graph are defined. Then, the proposed algorithm is applied in the line graph to propagate the label of certain labeled nodes to the whole network until convergence, and the final label of a given node is its community id. It worth mentioning that our algorithm is very fast and with almost linear time complexity. Extensive simulations using both synthetic and real-world benchmark networks are performed to verify the algorithmic performance.
ClausetA., NewmanM.E.J. and MooreC., Finding community structure in very large networks, Physical Review E70(6) (2004), 066111.
2.
LancichinettiA. and FortunatoS., Community detection algorithms: A comparative analysis, Physical Review E80(5) (2009), 056117.
3.
LancichinettiA., FortunatoS. and RadicchiF., Benchmark graphs for testing community detection algorithms, Physical Review E78(4) (2008), 046110–046115.
4.
YangB., LiuJ.M. and LiuD.Y., Characterizing and Extracting Multiplex Patterns in Complex Networks, IEEE Transactions on Systems, Man, and Cybernetics, Part B42(2) (2012), 469–481.
5.
KnuthD.E., The stanford GraphBase: A platform for combinatorial computing, Reading, MA: Addison-Wesley Professional37 (1993), 592.
6.
HeD., LiuD., ZhangW., JinD. and YangB., Discovering link communities in complex networks by exploiting link dynamics, Journal of Statistical Mechanics: Theory and Experiment10 (2012), 10015.
7.
HeD., JinD., ChenZ. and ZhangW., Identification of hybrid node and link communities in complex networks, Scientific Reports5(8638) (2015), 1–14.
8.
LiuD., BaiH.Y., LiH.J. and WangW.J., Semi-supervised community detection using label propagation, International Journal of Modern Physics B28(29) (2014), 1450208.
9.
LusseauD., SchneiderK., BoisseauO.J., HaaseP., SlootenE. and DawsonS.M., The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations, Behavioral Ecology and Sociobiology54(4) (2003), 396–405.
10.
AgarwalG. and KempeD., Modularity-maximizing graph communities via mathematical programming, The European Physical Journal B66(3) (2008), 409–418.
11.
PallaG., BarabásiA.L. and VicsekT., Quantifying social group evolution, Nature446 (2007), 664–667.
12.
LiH.J., WangY., WuL.Y., ZhangJ. and ZhangX.S., Potts model based on a Markov process computation solves the community structure problem effectively, Physical Review E86(1) (2012), 016109.
13.
LiH.J. and ZhangX.S., Analysis of stability of community structure across multiple hierarchical levels, Europhysics Letters103(5) (2013), 58002.
14.
DuchJ. and ArenasA., Community detection in complex networks using extremal optimization, Physical Review E72(2) (2005), 027104.
15.
HofmanJ.M. and WigginsC.H., Bayesian approach to network modularity, Physical Review Letters100(25) (2008), 258701.
16.
KeenerJ.P., The Perron-Frobenius theorem and the ranking of football teams, SIAM Review35(1) (1993), 80–93.
17.
SuJ. and HavensT.C., Quadratic program-based modularity maximization for fuzzy community detection in social networks, IEEE Transactions on Fuzzy Systems23(5) (2015), 1356–1371.
18.
WhangJ., GleichD. and DhillonI., Overlapping community detection using neighborhood-inflated seed expansion, IEEE Transactions on Knowledge and Data Engineering28(5) (2015), 1272–1284.
19.
HastingsM.B., Community detection as an inference problem, Physical Review E74(3) (2006), 035102.
20.
BogunaM., Pastor-SatorrasR., Diaz-GuileraA. and ArenasA., Models of social networks based on social distance attachment, Physical review E70(5) (2004), 056122.
21.
NewmanM.E.J., Fast algorithm for detecting community structure in networks, Physical Review E69(6) (2004), 066133.
22.
NewmanM.E.J. and GirvanM., Finding and evaluating community structure in networks, Physical Review E69(2) (2004), 026113.
23.
GirvanM. and NewmanM.E.J., Community structure in social and biological networks, Proceedings of the National Academy of Sciences of the United States of America99(12) (2002), 7821–7826.
24.
GleiserP. and DanonL., List of edges of the network of jazz musicians, Advances in Complex Systems6 (2003), 565.
25.
RonhovdeP. and NussinovZ., Local resolution-limit-free Potts model for community detection, Physical Review E81(4) (2010), 046114.
26.
GuimeraR. and NunesL.A., Amaral, Functional cartography of complex metabolic networks, Nature433(7028) (2005), 895–900.
27.
GuimeraR., DanonL., Diaz-GuileraA., GiraltF. and ArenasA., Self-similar community structure in a network of human interactions, Physical Review E68(6) (2003), 065103.
28.
BhatS.Y. and AbulaishM., HOCTracker: Tracking the evolution of hierarchical and overlapping communities in dynamic social networks, IEEE Transactions on Knowledge and Data Engineering27(4) (2015), 1019–1013.
29.
EvansT.S. and LambiotteR., Line graphs, link partitions, and overlapping communities, Physical Review E80(1) (2009), 016105.
30.
EvansT.S. and LambiotteR., Line graphs of weighted networks for overlapping communities, European Physical Journal B77(2) (2010), 265.
31.
RaghavanU.N., AlbertR. and KumaraS., Near linear time algorithm to detect community structures in large-scale networks, Physical Review E76(3) (2007), 036106.
32.
ZacharyW., An information flow model for conflict and fission in small groups, Journal of Anthropological Research1 (1977), 452–473.
33.
AhnY.Y., BagrowJ.P. and LehmannS., Link communities reveal multiscale complexity in networks, Nature466(7307) (2010), 761–764.
34.
LiZ., ZhangX.S., WangR.S., LiuH. and ZhangS., Discovering link communities in complex networks by an integer programming model and a genetic algorithm, PloS One8(12) (2013), e83739.
