An Improved Method Based on Label Propagation and Greedy Approaches for Community Detection in Dynamic Social Networks
Subject Areas : General
Mohammad ستاری
1
*
,
kamran zamanifar
2
1 -
2 -
Keywords: GreedyLabelRankT, LabelRankT, Label Propagation Approach, Community Detection, Dynamic Social Network.,
Abstract :
Community detection in temporal social networks is one of the most important topics of research which attract many researchers around the world. There are variety of approaches in detecting communities in dynamic social network among which label propagation approach is simple and fast approach. This approach consists of many methods such as LabelRankT is one with high speed and less complexity. Similar to most methods for detecting communities in dynamic social networks, this one is not trouble free. That is, it is not considered the internal connection of communities, when it expands communities of the previous snapshots in the current snapshot. This drawback decreases the accuracy of community detection in dynamic social networks. For solving the drawback, a greedy approach based on local modularity optimization is added to LabelRankT method. Here, the newly proposed GreedyLabelRankT, LabelRankT and non-overlapping version of Dominant Label Propagation Algorithm Evolutionary (DLPAE-Non Overlapping) on real and synthetic datasets are implemented. Experimental results on both real and synthetic network show that the proposed method detect communities more accurately compared to the benchmark methods. Moreover, the finding here show that running time of the proposed method is close to LabelRankT. Therefore, the proposed method increase the accuracy of community detection in dynamic social networks with no noticeable change in the running time of that.
[1] M. E. Newman, and M. Girvan, "Finding and evaluating community structure in networks", Physical review E, vol.69 , no.2, p.026113, 2004.
[2] S. Fortunato, “Community detection in graphs,” Physics Reports, pp. 75-174,2010. [3] N. P. Nguyen, T. N. Dinh, Y. Shen, and M. T. Thai, “Dynamic social community detection and its applications.”, PLoS One, vol. 9, no.4, p. e91431, 2014.
[4] V. D. Blondel, J. Guillaume, and E. Lefebvre, “Fast unfolding of communities in large networks,” Journal of Statistical Mechanics: Theory and Experiment, no. 10, pp. 1–12, 2008.
[5] S. Soundarajan, and J. E. Hopcroft, "Use of local group information to identify communities in networks". ACM Transactions on Knowledge Discovery from Data (TKDD), vol. 9, no.3, pp 1-35, 2015.
[6] U. N. Raghavan, R. Albert, and S. Kumara, Near linear time algorithm to detect community structures in large-scale networks, Physical review E, vol. 76, no.3, p.036106, 2007.
[7] M. Sattari, K. Zamanifar, “A spreading activation-based label propagation algorithm for overlapping community detection in dynamic social networks”, Data & Knowledge Engineering, vol. 113, pp.155-170, 2018.
[8] M. Sattari, K. Zamanifar. “A cascade information diffusion based label propagation algorithm for community detection in dynamic social networks”, Journal of Computational Science. vol. 25, pp. 122-33, 2018.
[9] X. Ma, D. Dong, “Evolutionary nonnegative matrix factorization algorithms for community detection in dynamic networks”. IEEE Transactions on Knowledge and Data Engineering, vol. 29, no. 5, pp. 1045-58, 2017.
[10] G. Rossetti, L. Pappalardo, Pedreschi D, Giannotti F. “Tiles: an online algorithm for community discovery in dynamic social networks”, Machine Learning. vol. 106, no. 8, pp. 1213-41, 2017.
[11] K. Kuzmin, S. Y. Shah, and B. K. Szymanski,"Parallel overlapping community detection with SLPA". In Social Computing (SocialCom), pp. 204-212, 2013.
[12] J. Xie, M. Chen, and B. Szymanski, “LabelrankT: Incremental community detection in dynamic networks via label propagation,” In Proceedings of the ACM Workshop on Dynamic Networks Management and Mining, ACM, pp. 25–32, 2013.
[13] J. Xie, and B. K. Szymanski, “LabelRank: A stabilized label propagation algorithm for community detection in Networks,” In Network Science Workshop (NSW), IEEE, pp. 138-143, 2013.#3 [14] M. Takaffoli, R. Rabbany, and O. R. Za, “Incremental local community identification in dynamic social networks.” In Proceedings of the IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, IEEE/ACM pp. 90-94, 2013.
[15] H. Alvari, A. Hajibagheri, and G. Sukthankar, “Community detection in dynamic social networks: A game-theoretic approach,” In Advances in Social Networks Analysis and Mining (ASONAM), IEEE/ACM , pp. 101–107, 2014.
[16] R. I. Lung, C. Chira, and A. Andreica, "Game theory and extremal optimization for community detection in complex dynamic networks". PloS one, vol.9, no.2, pp. 891-901, 2014.
[17] M. Takaffoli, R. Rabbany, and O. R. Za, “Incremental local community identification in dynamic social networks.” In Proceedings of the IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, IEEE/ACM pp. 90-94, 2013.
[18] J. He and D. Chen, “A fast algorithm for community detection in temporal network”, PhysicaA: Statistical Mechanics and its Applications, vol. 429, pp. 87–94, 2015.
[19] LXY.Leung, P.Hui, P.Liu , and J.Crowcroft, "Towards real-time community detection in large networks.", Physical Review E , vol. 79, no. 6, p.066107, 2009.
[20] K. Liu, J. Huang, H. un, M. Wan, Y. Qi, and H. Li, “Label propagation based evolutionary clustering for detecting overlapping and non-overlapping communities in dynamic networks,” Knowledge-Based Systems, vol. 89, pp. 487–496, 2015.
[21] S. H.L, H. J.B, T. Y.Q., Q.B., and L.Huai-Liang, “Detecting overlapping communities in networks via dominant label propagation,” Chinese Phys.B, vol. 24, no.1, p. 18703, 2015.
[22] X. Niu, W. Si, and C.Q. Wu, 2017. A label-based evolutionary computing approach to dynamic community detection. Computer Communications, vol. 108, pp.110-122, 2017.
[23] J. Han, W. Li, L. Zhao, Z. Su, Y. Zou, and W. Deng, "Community detection in dynamic networks via adaptive label propagation", PloS one, vol.12, no.11, p.e0188655,2017.
[24] M. Takaffoli, R. Rabbany, and O. R. Za, “Incremental local community identification in dynamic social networks.” In Proceedings of the IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, IEEE/ACM pp. 90-94, 2013.
[25] J. Gehrke, P. Ginsparg and J. Kleinberg, "Overview of the 2003 KDD Cup", ACM SIGKDD Explorations Newsletter, vol. 5, no. 2, pp.149-151, 2003.
[26] J. Leskovec, J. Kleinberg and C. Faloutsos. "Graphs over Time: Densification Laws, Shrinking Diameters and Possible Explanations.", ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), ACM, pp. 177-187, 2005
[27] A. Lancichinetti, S. Fortunato, "Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities", Phys. Rev. E, vol. 80, no.1, p. 016118, 2009.
[28] L. Danon, A. Diaz-Guilera, J. Duch, and A. Arenas. Comparing community structure identification. Journal of Statistical Mechanics: Theory and Experiment, 2005(09):P09008, 2005
[29] M. Newman, "modularity and community structure in networks". Proceedings of the National Academy of Sciences, vol. 103, no. 23, pp. 8577 –8582, 2002.