شناسائی انجمن در شبکه های دوبخشی با استفاده از معیار مرکزیت هلرنک
محورهای موضوعی : فناوری اطلاعات و ارتباطات
علی خسروزاده
1
(گروه مهندسی کامپیوتر، واحد قزوین، دانشگاه آزاد اسلامی، قزوین، ایران)
علی موقر
2
(گروه مهندسی کامپیوتر، دانشگاه صنعتی شریف، تهران، ایران)
محمدمهدی گیلانیان صادقی
3
(گروه مهندسی کامپیوتر، واحد قزوین، دانشگاه آزاد اسلامی، قزوین، ایران)
حمیدرضا ماهیار
4
(گروه مهندسی کامپیوتر، دانشگاه مک مستر، همیلتون، انتاریو، کانادا)
کلید واژه: شبکه های اجتماعی, گراف های دوبخشی, معیار مرکزیت, شناسائی انجمن, رای گیری,
چکیده مقاله :
ساختار انجمن ویژگی مشترک و مهمی در بسیاری از شبکه های پیچیده از جمله شبکه های دوبخشی است. شناسائی انجمن ها در سال‌های اخیر در بسیاری زمینه‌ها مورد توجه قرار گرفته و روش‌های زیادی برای این منظور پیشنهاد شده است، اما مصرف سنگین زمان در برخی روش ها، استفاده از آنها را در شبکه‌های بزرگ مقیاس محدود می‌کند. روش‌هائی با پیچیدگی کمتر وجود دارند اما اکثراً غیرقطعی هستند که کاربرد آنها در دنیای واقعی را کاهش می‌دهد. رویکرد معمول اتخاذ شده برای شناسائی انجمن ها در شبکه‌های دوبخشی این است که ابتدا یک طرح ریزی یک‌بخشی از شبکه ساخته شود و سپس انجمن ها در آن طرح ریزی با استفاده از روش‌های مربوط به شبکه‌های یک‌بخشی شناسائی شوند. این طرح ریزی ها به طور ذاتی اطلاعات را از دست می‌دهند. در این مقاله بر اساس معیار ماژولاریتی دوبخشی که قدرت تقسیم بندی ها را در شبکه های دوبخشی محاسبه می کند و با استفاده از معیار مرکزیت هلرنک، روشی سریع و قطعی برای شناسائی انجمن ها از شبکه های دوبخشی بطور مستقیم و بی نیاز از طرح ریزی ارائه گردیده است. روش پیشنهادی از فرآیند رأی گیری در فعالیت های انتخاباتی در جامعه اجتماعی الهام گرفته و آن را شبیه سازی می کند. نتایج آزمایشات نشان می دهد، مقدار ماژولاریتی انجمن های حاصل و دقت شناسائی تعداد آنها در روش پیشنهادی بهبود یافته است.
Community structure is a common and important feature in many complex networks, including bipartite networks. In recent years, community detection has received attention in many fields and many methods have been proposed for this purpose, but the heavy consumption of time in some methods limits their use in large-scale networks. There are methods with lower time complexity, but they are mostly non-deterministic, which greatly reduces their applicability in the real world. The usual approach that is adopted to community detection in bipartite networks is to first construct a unipartite projection of the network and then communities detect in that projection using methods related to unipartite networks, but these projections inherently lose information. In this paper, based on the bipartite modularity measure that quantifies the strength of partitions in bipartite networks and using the HellRank centrality measure, a quick and deterministic method for community detection from bipartite networks directly and without need to projection, proposed. The proposed method is inspired by the voting process in election activities in the social society and simulates it.
[1] S. Fortunato, "Community Detection in Graphs," Physics Reports, vol. 486, pp. 75-174, 2002.
[2] M. J. Barber, "Modularity and Community Detection in Bipartite Networks," Physical Review E, vol. 76, 2007.
[3] M. Girvan and M. E. Newman, "Community Structure in Social and Biological Networks," In Proceedings of the National Academy of Sciences of USA, 2002, vol. 99, pp. 7821-7826.
[4] J. Shang, L. Liu, X. Li, F. Xie and C. Wu, "Epidemic Spreading on Complex Networks with Overlapping and non-Overlapping Community Structure," Physica A: Statistical Mechanics and its Applications, vol. 419, pp. 171-182, 2015.
[5] A. Clauset and M. E. Newman, "Finding Community Structure in Very Large Networks," Physical Review E, vol. 70, 2004.
[6] M. Newman and M. Girvan, "Finding and Evaluating Community Structure in Networks," Physical Review E, vol. 69, 2004.
[7] G. Palla, I. Derenyi, I. Farkas and T. Vicsek, "Uncovering the Overlapping Community Structure of Complex Networks in Nature and Society," Nature, vol. 435, pp. 814-818, 2005.
[8] M. E. Newman, "Detecting Community Structure in Networks," The European Physical Journal B, vol. 38, pp. 321-330, 2004.
[9] L. Danon, A. Diaz-Guilera, J. Duch and A. Arenas, "Comparing Community Structure Identification," Journal of Statistical Mechanics: Theory and Experiment, vol. 9, 2005.
[10] R. Guimera and M. Sales-Pardol, "Module Identification in Bipartite and Directed Networks," Physical Review E, vol. 76, 2007.
[11] 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, 2007.
[12] M. J. Barber, "Detecting Network Communities by Propagating Labels Under Constraints," Physical Review E, vol. 80, 2009.
[13] X. Liu and T. Murata, "Community Detection in Large-Scale Bipartite Networks," Information and Media Technologies, vol. 5, pp. 184-192, 2010.
[14] A. Silva, S. Guimaraes, W. Meira and M. Zaki, "Profilerank: Finding Relevant Content and Influential Users," In Proceedings of the 7th Workshop on Social Network Mining and Analysis, 2013, pp. 1-9.
[15] D. Wei, X. Deng, X. Zhang, Y. Deng and S. Mahadevan, "Identifying Influential Nodes in Weighted Networks Based on Evidence Theory," Physica A: Statistical Mechanics and its Applications, vol. 392, pp. 2564-2575, 2013.
[16] Y. Yustiawan, W. Maharani and A. A. Gozali, "Degree Centrality for Social Network with Opsahl Method," Procedia Computer Science, vol. 59, pp. 419-426, 2015.
[17] H. Mahyar, "Detection of Top-k Central Nodes in Social Networks: A Compressive Sensing Approach," IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, 2015, pp. 902-909.
[18] M. Cha, H. Haddadi, F. Benevenuto and K. P. Gummadi, "Measuring User Influence in Twitter" In Proceedings of the 4th International AAAI Conference on Weblogs and Social, 2010, pp. 10-17.
[19] N. E. Friedkin and E. C. Johnsen, Social Influence Network Theory: A Sociological Examination of Small Group Dynamics, Cambridge University Press, 2011.
[20] K. Zhao, X. Wang, M. Yu and B. Gao, "User Recommendations in Reciprocal and Bipartite Social Networks - An Online Dating Case Study," IEEE Intelligent Systems, vol. 29, pp. 27-35, 2014.
[21] K. Wehmuth and A. Ziviani, "Daccer: Distributed Assessment of the Closeness Centrality Ranking in Complex Networks," Computer Networks, vol. 57, pp. 2536-2548, 2013.
[22] A. Muruganantham and G. Gandi, "Ranking the Influence Users in a Social Networking Site Using an Improved Topsis Method," Journal of Theoretical and Applied Information, vol. 1073, pp. 1-11, 2015.
[23] H. Mahyar, H. R. Rabiee, A. Movaghar, E. Ghalebi and A. Nazemian, "Cs-Comdet: A Compressive Sensing Approach for Intercommunity Detection in Social Networks," IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, 2015, pp. 89-96.
[24] M. Kitsak, L. K. Gallos, S. Havlin, F. Liljeros, L. Muchnik, H. E. Stanley and H. A. Makse, "Identifying Influential Spreaders in Complex Networks," Nature Physics, vol. 6, pp. 888-893, 2010.
[25] T. Zhou, J. Ren and M. Medo, "Bipartite Network Projection and Personal Recommen-dation," Physical Review E, vol. 76, 2007.
[26] M. Kitsak and D. Krioukov, "Hidden Variables in Bipartite Networks," Physical Review E, vol. 84, 2011.
[27] T. Opsahl, "Triadic Closure in Two-Mode Networks: Redefining the Global and Local Clustering Coefficients," Social Networks, vol. 35, pp. 159-167, 2013.
[28] J. Liebig and A. Rao, "Identifying Influential Nodes in Bipartite Networks Using the Clustering Coefficient," In Proceedings of 10th International Conference on Signal-Image Technology and Internet-Based Systems, 2014, pp. 323-330.
[29] S. M. Taheri and H. Mahyar, "Hellrank: A Hellinger-Based Centrality Measure for Bipartite Social Networks," Social Network Analysis and Mining, vol. 7, 2017.
[30] M. Nikulin, Hellinger distance, Encyclopedia of Mathematics, 2001.
[31] M. E. Newman, "Fast Algorithm for Detecting Community Structure in Networks," Physical Review E, vol. 69, 2004.
[32] J. M. Pujol, J. Bejar and J. Delgado, "Clustering Algorithm for Determining Community Structure in Large Networks," Physical Review E, vol. 74, 2006.
[33] M. E. Newman, "Finding Community Structure in Networks Using the Eigenvectors of Matrices," Physical Review E, vol. 74, 2006.
[34] J. Kleinberg and S. Lawrence, "The Structure of the Web," Science, vol. 294, pp. 1849-1850, 2001.
[35] P. Chen and S. Render, "Community Structure of the Physical Review Citation Network," Journal of Informetrics, vol. 4, pp. 278-290, 2010.
[36] E. Ravasz, A. L. Somera, D. A. Mongru, Z. N. Oltvai and A. L. Barabasi, "Hierarchical Organization of Modularity in Metabolic Networks," Science, vol. 297, pp. 1551-1555, 2002.
[37] R. Guimera and L. A. Amaral, "Functional Cartography of Complex Metabolic Networks," Nature, vol. 433, pp. 895-900, 2005.
[38] A. C. Lewis, N. S. Jones, M. A. Porter and C. M. Deane, "The Function of Communities in Protein Interaction Networks at Multiple Scales," BMC Systems Biology, vol. 4, 2010.
[39] P. Gleiser and L. Danon, "Community Structure in Jazz," Advances in Complex Systems, vol. 6, pp. 565-573, 2003.
[40] A. Nematzadeh, E. Ferrara, A. Flammini and Y. Y. Ahn, "Optimal Network Modularity for Information Diffusion," Physical Review Letters, vol. 113, 2014.
[41] G. Ren and X. Wang, "Epidemic Spreading in Time-Varying Community Networks," Chaos: An Interdisciplinary Journal of Nonlinear Science, vol. 24, 2014.
[42] T. Zhou, M. Zhao, G. Chen, G. Yan and B. H. Wang, "Phase Synchronization on Scale-Free Networks with Community Structure," Physics Letters A, vol. 368, pp. 431-434, 2007.
[43] H. Liang Sun, E. Ch’ng, X. Yong, J. M. Garibaldi, S. See and D. Bing Chen, "A Fast Community Detection Method in Bipartite Networks by Distance Dynamics," Physica A: Statistical Mechanics and its Applications, vol. 496, pp. 108-120, 2018.
[44] L. Y. Tang, S. N. Li, J. H. Lin and Q. Guo, "Community Structure Detection Based on the Neighbor Node Degree Information," International Journal of Modern Physics C, vol. 27, 2016.
[45] H. Peng, D. Zhao, L. Li and J. Lu, "An Improved Label Propagation Algorithm Using Average Node Energy in Complex," Physica A: Statistical Mechanics and its Applications, vol. 460, pp. 98-104, 2016.
[46] W. Li, C. Huang and M. Wang, "Stepping Community Detection Algorithm Based on Label Propagation," Physica A: Statistical Mechanics and its Applications, vol. 472, pp. 145-155, 2017.
[47] J. X. Yang and X. D. Zhang, "Finding Overlapping Communities Using Seed Set," Physica A: Statistical Mechanics and its Applications, vol. 467, pp. 96-106, 2017.
[48] S. Bilal and M. Abdelouahab, "Evolutionary Algorithm and Modularity for Detecting Communities in Networks," Physica A: Statistical Mechanics and its Applications, vol. 473, pp. 89-96, 2017.
[49] W. Chen, Z. Liu, X. Sun and Y. Wang, "A Game-Theoretic Framework to Identify Overlapping Communities in Social Networks," Data Mining and Knowledge Discovery, vol. 21, pp. 224-240, 2010.
[50] H. L. Sun, E. Ch’ng, X. Yong, J. M. Garibaldi and S. See, "An Improved Game-Theoretic Approach to Uncover Overlapping Communities," International Journal of Modern Physics C, vol. 28, 2017.
[51] T. S. Evans and R. Lambiotte, "Line Graphs, Link Partitions and Overlapping Communities," Physical Review E, vol. 80, 2009.
[52] V. D. Blondel, J. L. Guillaume, R. Lambiotte and E. Lefebvre, "Fast Unfolding of Communities in Large Networks," Journal of Statistical Mechanics: Theory and Experiment, vol. 10, 2008.
[53] A. Mukherjee, M. Choudhury and N. Ganguly, "Understanding How Both the Partitions of a Bipartite Network Affect its One-Mode Projection," Physica A: Statistical Mechanics and its Applications, vol. 390, pp. 3602-3607, 2011.
[54] X. Wang and X. Qin, "Asymmetric intimacy and algorithm for detecting communities in bipartite networks," Physica A: Statistical Mechanics and its Applications, vol. 462, pp. 569-578, 2016.
[55] M. E. Newman, "Modularity and Community Structure in Networks," In Proceedings of the National Academy of Sciences of USA, 2006, vol. 103, pp. 8577-8582.
[56] S. Fortunato and M. Barthelemy, "Resolution Limit in Community Detection," In Proceedings of the National Academy of Sciences of USA, 2007, vol. 104, pp. 36-41.
[57] S. Lehmann, M. Schwartz and L. K. Hansen, "Biclique Communities," Physical Review E, vol. 78, 2008.
[58] P. Zhang, J. Wang, X. Li, M. Li and Z. Di, "Clustering Coefficient and Community Structure of Bipartite Networks," Physica A: Statistical Mechanics and its Applications, vol. 387, pp. 6869-6875, 2008.
[59] Y. Cui and X. Wang, "Uncovering Overlapping Community Structures by the Key Bi-Community and Intimate Degree in Bipartite Networks," Physica A: Statistical Mechanics and its Applications, vol. 407, pp. 7-14, 2014.
[60] D. B. Larremore and A. Clauset, "Efficiently Inferring Community Structure in Bipartite Networks," Physical Review E, vol. 90, 2014.
[61] Y. Xu, L. Chen, B. Li and W. liu, "Density-Based Modularity for Evaluating Community Structure in Bipartite Networks," Information Sciences, vol. 317, pp. 278-294, 2015.
[62] J. G. Liu, L. Hou, X. Pan, Q. Guo and T. Zhou, "Stability of Similarity Measurements for Bipartite Networks," Nature, vol. 6, 2016.
[63] K. Li and Y. Pang, "A Unified Community Detection Algorithm in Complex Network," Neurocomputing, vol. 130, pp. 36-43, 2014.
[64] X. Han, S. Cao, Z. Shen, B. Zhang and W. X. Wang, "Emergence of Communities and Diversity in Social Networks," In Proceedings of the National Academy of Sciences of USA, 2017, vol. 114, pp. 2887-2891.
[65] D. Chen, Y. Fu and M. Shang, "A Fast and Efficient Heuristic Algorithm for Detecting Community," Physica A: Statistical Mechanics and its Applications, vol. 388, pp. 2741-2749, 2009.
[66] D. Chen, M. Shang, Z. Lv and Y. Fu, "Detecting Overlapping Communities of Weighted Networks via a Local Algorithm," Physica A: Statistical Mechanics and its Applications, vol. 389, pp. 4177-4187, 2010.
[67] J. He and D. Chen, "A Fast Algorithm for Community Detection in Temporal Network," Physica A: Statistical Mechanics and its Applications, vol. 429, pp. 87-94, 2015.
[68] J. He, D. Chen, C. Sun, Y. Fu and W. Li, "Efficient Stepwise Detection of Communities in Temporal Networks," Physica A: Statistical Mechanics and its Applications, vol. 469, pp. 438-446, 2017.
[69] R. Shang, W. Zhang, L. Jiao, R. Stolkin and Y. Xue, "A Community Integration Strategy Based on an Improved Modularity Density Increment for Large-Scale Networks," Physica A: Statistical Mechanics and its Applications, vol. 469, pp. 471-485, 2017.
[70] Y. Pan, D. H. Lia, J. G. Liu and J. Z. Liang, "Detecting Community Structure in Complex Networks via Node Similarity," Physica A: Statistical Mechanics and its Applications, vol. 389, pp. 2849-2857, 2010.
[71] B. H. Good and Y. A. de Montjoye, "Performance of Modularity Maximization in Practical Contexts," Physical Review E, vol. 81, 2010.
[72] J. Shang, L. Liu, X. Li and F. Xie, "Targeted Revision: A Learning Based Approach for Incremental Community Detection," Physica A: Statistical Mechanics and its Applications, vol. 443, pp. 70-85, 2016.
[73] C. Zhou, L. Feng and Q. Zhao, "A Novel Community Detection Method in Bipartite Networks," Physica A: Statistical Mechanics and its Applications, vol. 492, pp. 1679-1693, 2018.
[74] M. J. Barber, M. Faria and L. Streit, "Searching for Communities in Bipartite Networks," AIP Conference Proceedings, 2008, vol. 1021.
[75] P. Zhang, "Evaluating Accuracy of Community Detection Using the Relative Normalized Mutual Information," Journal of Statistical Mechanics: Theory and Experiment, vol. 11, 2015.
[76] A. Davis, B. B. Gardner and M. R. Gardner, Deep South: A Social Anthropological Study of Caste and Class, in: A Study in the Sociology of Science, University of South Carolina Press, 1941.
[77] J. Kunegis, "Konect: the Koblenz Network Collection," Proceedings of the 22th International Conference on World Wide Web, 2013, pp. 1343-1350.
[78] J. Scott and M. Hughes, The Anatomy of Scottish Capital: Scottish Companies and Scottish, McGill-Queen’s University Press, 1980.