A hybrid method for community detection based on user interactions, topology and frequent pattern mining

Document Type : Computer Article

Authors

Department of Computer Engineering, Central Tehran Branch, Islamic Azad University, Tehran, Iran.

Abstract

In recent years, community detection in social networks has become one of the most important research areas. One of the ways to community detection is to use interactions between users. There are different types of interactions in social networks, which, if used together with network topology, improve the precision of community identification. In this paper, a new method based on the combination of user interactions and network topology is proposed to community detection. In the community formation stage, the effective nodes are identified based on eigenvector centrality, and the primary communities around these nodes are formed based on frequent pattern mining. In the community expansion phase, small communities expand using modularity and the degree of interactions among users. To calculate the degree of interaction between users, a new measure based on the local clustering coefficient and interactions between common neighbors is proposed, which improves the accuracy of the degree of user interactions. Analysis of Higgs Twitter and Flickr datasets utilizing internal density metric, NMI and Omega demonstrates that the proposed method outperforms the other five community detection methods.

Keywords

Main Subjects

References

[1] Li, XiaoMing, Guangquan Xu, and Minghu Tang, "Community detection for multi-layer social network based on local random walk", Journal of Visual Communication and Image Representation. 57 (2018): 91-98.
[2] Dabaghi-Zarandi, Fahimeh, and Parsa KamaliPour, "Community detection in complex network based on an improved random algorithm using local and global network information", Journal of Network and Computer Applications. 206 (2022): 103492.
[3] Aggarwal, Charu C,An introduction to social network data analytics,Springer, 2011.
[4] Moscato, Vincenzo, and Giancarlo Sperlì, "A survey about community detection over On-line Social and Heterogeneous Information Networks", Knowledge-Based Systems. 224 (2021): 107112.
[5] Luo, Linbo, Kexin Liu, Bin Guo, and Jianfeng Ma, "User interaction-oriented community detection based on cascading analysis", Information Sciences. 510 (2020): 70-88.
[6] گلکار، ایمان و  مرجان کائدی. " ارائه مدلی برای تخمین میزان برون‌گرایی اعضای شبکه اجتماعی با استفاده از اطلاعات ساختار گراف". نشریه مدل‌سازی در مهندسی 13، 43، (1394): 91-106. (inPersian)
[7] Wilson, Christo, Alessandra Sala, Krishna P. N. Puttaswamy, and Ben Y. Zhao, "Beyond Social Graphs", ACM Transactions on the Web. 6 (2012): 1-31.
[8] Ahmed, Cherry, and Abeer ElKorany, "Enhancing link prediction in Twitter using semantic user attributes".Proceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2015, 1155-1161, 2015.
[9] O’Riordan, Sheila, Joseph Feller, and Tadhg Nagle, "A categorisation framework for a feature-level analysis of social network sites", Journal of Decision Systems. 25 (2016): 244-262.
[10] Moosavi, Seyed Ahmad, and Mehrdad Jalali, "Community detection in online social networks using actions of users".2014 Iranian Conference on Intelligent Systems (ICIS), 1-7, (IEEE), 2014.
[11] Dev, Himel, Mohammed Eunus Ali, and Tanzima Hashem, "User interaction based community detection in online social networks".Database Systems for Advanced Applications: 19th International Conference, DASFAA 2014, Bali, Indonesia, April 21-24, 2014. Proceedings, Part II 19, 296-310, (Springer), 2014.
[12] Vathi, Eleni, Georgios Siolas, Andreas Stafylopatis, Ngoc-Thanh Nguyen, Manuel Núñez, and Bogdan Trawiński, "Mining and categorizing interesting topics in Twitter communities", Journal of Intelligent & Fuzzy Systems. 32 (2017): 1265-1275.
[13] Moosavi, Seyed Ahmad, Mehrdad Jalali, Negin Misaghian, Shahaboddin Shamshirband, and Mohammad Hossein Anisi, "Community detection in social networks using user frequent pattern mining", Knowledge and Information Systems. 51 (2017): 159-186.
[14] Wang, Yang, Zengru Di, and Ying Fan, "Identifying and characterizing nodes important to community structure using the spectrum of the graph", Public Library of Science. 6 (2011): e27418.
[15] Ai, Jun, Tao He, Zhan Su, and Lihui Shang, "Identifying influential nodes in complex networks based on spreading probability", Chaos, Solitons & Fractals. 164 (2022): 112627.
[16] Xia, Yingjie, Xiaolong Ren, Zhengchao Peng, Jianlin Zhang, and Li She, "Effectively identifying the influential spreaders in large-scale social networks", Multimedia Tools and Applications. 75 (2016): 8829-8841.
[17] Hansen, Derek, Ben Shneiderman, and Marc A Smith,Analyzing Social Media Networks with NodeXL: Insights from a Connected World (Second Edition),(Morgan Kaufmann 2020), pp.Chapter 3.
[18] Ahajjam, Sara, Mohamed El Haddad, and Hassan Badir, "A new scalable leader-community detection approach for community detection in social networks", Social Networks. 54 (2018): 41-49.
[19] Zhong, Lin-Feng, Ming-Sheng Shang, Xiao-Long Chen, and Shi-Ming Cai, "Identifying the influential nodes via eigen-centrality from the differences and similarities of structure", Physica A: Statistical Mechanics and its Applications. 510 (2018): 77-82.
[20] Goyal, Amit, Francesco Bonchi, and Laks VS Lakshmanan, "Discovering leaders from community actions".Proceedings of the 17th ACM conference on Information and knowledge management, 499-508, 2008.
[21] Lu, Dongyuan, Qiudan Li, and Stephen Shaoyi Liao, "A graph-based action network framework to identify prestigious members through member's prestige evolution", Decision Support Systems. 53 (2012): 44-54.
[22] Bamakan, Seyed Mojtaba Hosseini, Ildar Nurgaliev, and Qiang Qu, "Opinion leader detection: A methodological review", Expert Systems with Applications. 115 (2019): 200-222.
[23] Kolahkaj, Maral, Ali Harounabadi, Alireza Nikravanshalmani, and Rahim Chinipardaz, "A hybrid context-aware approach for e-tourism package recommendation based on asymmetric similarity measurement and sequential pattern mining", Electronic Commerce Research and Applications. 42 (2020): 100978.
[24] Martínez, Víctor, Fernando Berzal, and Juan-Carlos Cubero, "A Survey of Link Prediction in Complex Networks", ACM Computing Surveys. 49 (2016): 1-33.
[25] صالحی، سید محمدمهدی و  علی‌اکبر پویان. " مروری بر روش‌های مدل‌سازی هم‌پوشانی در الگوریتم‌های انجمن‌یابی شبکه‌های اجتماعی". نشریه مدل‌سازی در مهندسی 17، 56 (1398): 247- 256. (inPersian)
[26] Paul, Amit, and Animesh Dutta, "Community detection using Local Group Assimilation", Expert Systems with Applications. 206 (2022): 117794.
[27] Tumiran, Siti Aisyah, and Bellie Sivakumar, "Community structure concept for catchment classification: A modularity density-based edge betweenness (MDEB) method", Ecological Indicators. 124 (2021): 107346.
[28] Arab, Mohsen, and Mohsen Afsharchi, "Community detection in social networks using hybrid merging of sub-communities", Journal of Network and Computer Applications. 40 (2014): 73-84.
[29] Dugué, Nicolas, and Anthony Perez, "Direction matters in complex networks: A theoretical and applied study for greedy modularity optimization", Physica A: Statistical Mechanics and its Applications. 603 (2022): 127798.
[30] Berahmand, Kamal, and Asgarali Bouyer, "A Link-Based Similarity for Improving Community Detection Based on Label Propagation Algorithm", Journal of Systems Science and Complexity. 32 (2018): 737-758.
 [31] Wu, Wenhui, Sam Kwong, Yu Zhou, Yuheng Jia, and Wei Gao, "Nonnegative matrix factorization with mixed hypergraph regularization for community detection", Information Sciences. 435 (2018): 263-281.
[32] Yakoubi, Zied, and Rushed Kanawati, "LICOD: A Leader-driven algorithm for community detection in complex networks", Vietnam Journal of Computer Science. 1 (2014): 241-256.
[33] Li, Wei, Ce Huang, Miao Wang, and Xi Chen, "Stepping community detection algorithm based on label propagation and similarity", Physica A: Statistical Mechanics and its Applications. 472 (2017): 145-155.
[34] Srilatha, Pulipati, and Ramakrishnan Manjula, "Similarity index based link prediction algorithms in social networks: A survey", Journal of Telecommunications and Information Technology. (2016): 87-94.
[35] Belfin, RV, and Piotr Bródka, "Overlapping community detection using superior seed set selection in social networks", Computers & Electrical Engineering. 70 (2018): 1074-1083.
[36] Pan, Xiaohui, Guiqiong Xu, Bing Wang, and Tao Zhang, "A Novel Community Detection Algorithm Based on Local Similarity of Clustering Coefficient in Social Networks", IEEE Access. 7 (2019): 121586-121598.
[37] Mishra, Sneha, Shashank Sheshar Singh, Shivansh Mishra, and Bhaskar Biswas, "TCD2: Tree-based community detection in dynamic social networks", Expert Systems with Applications. 169 (2021): 114493.
[38] Helal, Nivin A., Rasha M. Ismail, Nagwa L. Badr, and Mostafa G. M. Mostafa, "Leader‐based community detection algorithm for social networks", WIREs Data Mining and Knowledge Discovery. 7 (2017).
[39] Yang, Chen, Lei Liu, Li Chen, and Ben Niu, "A novel friend recommendation service based on interaction information mining".2017 International Conference on Service Systems and Service Management, 1-5, (IEEE), 2017.
[40] Lim, Kwan Hui, and Amitava Datta, "An interaction-based approach to detecting highly interactive Twitter communities using tweeting links", Web Intelligence. 14 (2016): 1-15.
[41] Bonacich, Phillip, "Power and centrality: A family of measures", American journal of sociology. 92 (1987): 1170-1182.
[42] Zaki, Mohammed Javeed, "Scalable algorithms for association mining", IEEE transactions on knowledge and data engineering. 12 (2000): 372-390.
[43] Telikani, Akbar, Amir H. Gandomi, and Asadollah Shahbahrami, "A survey of evolutionary computation for association rule mining", Information Sciences. 524 (2020): 318-352.
 
[44] Luo, Wenjian, Nannan Lu, Li Ni, Wenjie Zhu, and Weiping Ding, "Local community detection by the nearest nodes with greater centrality", Information Sciences. 517 (2020): 377-392.
[45]Malliaros, Fragkiskos D, and Michalis Vazirgiannis, "Clustering and community detection in directed networks: A survey", Physics reports. 533 (2013): 95-142.
[46] De Domenico, Manlio, Antonio Lima, Paul Mougel, and Mirco Musolesi, "The anatomy of a scientific rumor", Scientific reports. 3 (2013): 2980.
 [47] Platform, Stanford Network Analysis, and (SNAP)  higgs-twitter (Accessed February 18, 2023) (2015 ) http://snap.stanford.edu/data/higgs-twitter.html
[48] Tan, Chenhao, Jie Tang, Jimeng Sun, Quan Lin, and Fengjiao Wang, "Social action tracking via noise tolerant time-varying factor graphs".Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, 1049-1058, 2010.
[49] (ArnetMiner), AMiner  Flickr-large Accessed February 18, 2023 (2006) https://www.aminer.cn/data-sna#Flickr large
[50] Lancichinetti, Andrea, Santo Fortunato, and János Kertész, "Detecting the overlapping and hierarchical community structure in complex networks", New journal of physics. 11 (2009): 033015.
[51] Sun, Peng Gang, Xunlian Wu, Yining Quan, and Qiguang Miao, "Influence percolation method for overlapping community detection", Physica A: Statistical Mechanics and its Applications. 596 (2022): 127103.
[52] Singh, Dipika, and Rakhi Garg, "NI-Louvain: A novel algorithm to detect overlapping communities with influence analysis", Journal of King Saud University - Computer and Information Sciences. 34 (2022): 7765-7774.
 
Journal of Modeling in Engineering
Volume 21, Issue 75
December 2023
Pages 129-145

Files

History

  • Receive Date: 04 February 2023
  • Revise Date: 29 May 2023
  • Accept Date: 17 June 2023

Share

How to cite

Statistics