COGNISON: A Novel Dynamic Community Detection Algorithm in Social Network
محورهای موضوعی : Data Mining
Hamideh Sadat Cheraghchi
1
(shahid beheshti university)
Ali Zakerolhossieni
2
(shahid behesthi university)
کلید واژه: Social Network , Clustering , Cognitive Modeling , Evolution,
چکیده مقاله :
The problem of community detection has a long tradition in data mining area and has many challenging facet, especially when it comes to community detection in time-varying context. While recent studies argue the usability of social science disciplines for modern social network analysis, we present a novel dynamic community detection algorithm called COGNISON inspired mainly by social theories. To be specific, we take inspiration from prototype theory and cognitive consistency theory to recognize the best community for each member by formulating community detection algorithm by human analogy disciplines. COGNISON is placed in representative based algorithm category and hints to further fortify the pure mathematical approach to community detection with stabilized social science disciplines. The proposed model is able to determine the proper number of communities by high accuracy in both weighted and binary networks. Comparison with the state of art algorithms proposed for dynamic community discovery in real datasets shows higher performance of this method in different measures of Accuracy, NMI, and Entropy for detecting communities over times. Finally our approach motivates the application of human inspired models in dynamic community detection context and suggest the fruitfulness of the connection of community detection field and social science theories to each other.
The problem of community detection has a long tradition in data mining area and has many challenging facet, especially when it comes to community detection in time-varying context. While recent studies argue the usability of social science disciplines for modern social network analysis, we present a novel dynamic community detection algorithm called COGNISON inspired mainly by social theories. To be specific, we take inspiration from prototype theory and cognitive consistency theory to recognize the best community for each member by formulating community detection algorithm by human analogy disciplines. COGNISON is placed in representative based algorithm category and hints to further fortify the pure mathematical approach to community detection with stabilized social science disciplines. The proposed model is able to determine the proper number of communities by high accuracy in both weighted and binary networks. Comparison with the state of art algorithms proposed for dynamic community discovery in real datasets shows higher performance of this method in different measures of Accuracy, NMI, and Entropy for detecting communities over times. Finally our approach motivates the application of human inspired models in dynamic community detection context and suggest the fruitfulness of the connection of community detection field and social science theories to each other.
[1] Newman, M.E., Finding community structure in networks using the eigenvectors of matrices. Physical review E, 2006. 74(3): p. 036104.
#[2] Aynaud, T., et al., Communities in evolving networks: Definitions, detection, and analysis techniques, in Dynamics On and Of Complex Networks, Volume 2. 2013, Springer. p. 159-200.
#[3] Takaffoli, M., et al. Tracking changes in dynamic information networks. in Computational Aspects of Social Networks (CASoN), 2011 International Conference on. 2011. IEEE.
#[4] Greene, D., D. Doyle, and P. Cunningham. Tracking the evolution of communities in dynamic social networks. in Advances in Social Networks Analysis and Mining (ASONAM), 2010 International Conference on. 2010. IEEE.
#[5] Falkowski, T., J. Bartelheimer, and M. Spiliopoulou. Mining and visualizing the evolution of subgroups in social networks. in Proceedings of the 2006 IEEE/WIC/ACM International Conference on Web Intelligence. 2006. IEEE Computer Society.
#[6] Chakrabarti, D., R. Kumar, and A. Tomkins. Evolutionary clustering. in Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining. 2006. ACM.
#[7] Görke, R., et al., Dynamic graph clustering combining modularity and smoothness. Journal of Experimental Algorithmics (JEA), 2013. 18(1): p. 1.5.
#[8] Chi, Y., et al. Evolutionary spectral clustering by incorporating temporal smoothness. in Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining. 2007. ACM.
#[9] Lin, Y.-R., et al. Facetnet: a framework for analyzing communities and their evolutions in dynamic networks. in Proceedings of the 17th international conference on World Wide Web. 2008. ACM.
#[10] Papadopoulos, S., et al., Community detection in social media. Data Mining and Knowledge Discovery, 2012. 24(3): p. 515-554.
#[11] Lin, Y.-R., et al., Analyzing communities and their evolutions in dynamic social networks. ACM Transactions on Knowledge Discovery from Data (TKDD), 2009. 3(2): p. 8.
#[12] Zhang, J., et al. On-line Evolutionary Exponential Family Mixture. in IJCAI. 2009.
#[13] Newman, M.E., Fast algorithm for detecting community structure in networks. Physical review E, 2004. 69(6): p. 066133.
#[14] Cafieri, S., P. Hansen, and L. Liberti, Locally optimal heuristic for modularity maximization of networks. Physical Review E, 2011. 83(5): p. 056105.
#[15] Eaton, E. and R. Mansbach. A Spin-Glass Model for Semi-Supervised Community Detection. in AAAI. 2012.
#[16] Good, B.H., Y.-A. deMontjoye, and A. Clauset, Performance of modularity maximization in practical contexts. Physical Review E, 2010. 81(4): p. 046106.
#[17] Ning, H., et al., Incremental spectral clustering by efficiently updating the eigen-system. Pattern Recognition, 2010. 43(1): p. 113-127.
#[18] Tang, L., H. Liu, and J. Zhang, Identifying evolving groups in dynamic multimode networks. Knowledge and Data Engineering, IEEE Transactions on, 2012. 24(1): p. 72-85.
#[19] Hastings, M.B., Community detection as an inference problem. arXiv preprint cond-mat/0604429, 2006.
#[20] Krasnow, M.M., et al., Meeting now suggests we will meet again: Implications for debates on the evolution of cooperation. Scientific reports, 2013. 3.
#[21] Pachur, T., L.J. Schooler, and J.R. Stevens, We'll Meet Again: Revealing Distributional and Temporal Patterns of Social Contact. 2014.
#[22] Chi, Y., et al., On evolutionary spectral clustering. ACM Transactions on Knowledge Discovery from Data (TKDD), 2009. 3(4): p. 17.
#[23] Xu, K.S., M. Kliger, and A.O. Hero Iii, Adaptive evolutionary clustering. Data Mining and Knowledge Discovery, 2014. 28(2): p. 304-336.
#[24] Wu, M. and B. Schölkopf. A local learning approach for clustering. in Advances in neural information processing systems. 2006.
#[25] Strehl, A. and J. Ghosh, Cluster ensembles---a knowledge reuse framework for combining multiple partitions. The Journal of Machine Learning Research, 2003. 3: p. 583-617.
#[26] Yao, Y., Information-theoretic measures for knowledge discovery and data mining, in Entropy Measures, Maximum Entropy Principle and Emerging Applications. 2003, Springer. p. 115-136.
#[27] Eagle, N., A.S. Pentland, and D. Lazer, Inferring friendship network structure by using mobile phone data. Proceedings of the National Academy of Sciences, 2009. 106(36): p. 15274-15278.
#[28] More, J. and C. Lingam, Current trends in reality mining. 2013, IRJES.
#[29] Zhang, H., R. Dantu, and J.W. Cangussu, Socioscope: Human relationship and behavior analysis in social networks. Systems, Man and Cybernetics, Part A: Systems and Humans, IEEE Transactions on, 2011. 41(6): p. 1122-1143.
#[30] Kaufman, L. and P.J. Rousseeuw, Finding groups in data: an introduction to cluster analysis. Vol. 344. 2009: John Wiley & Sons.
#[31] Rousseeuw, P.J., Silhouettes: a graphical aid to the interpretation and validation of cluster analysis. Journal of computational and applied mathematics, 1987. 20: p. 53-65.
#[32] Newman, M.E., Modularity and community structure in networks. Proceedings of the National Academy of Sciences, 2006. 103(23): p. 8577-8582.
