More Web Proxy on the site http://driver.im/

research-article

Triangle-oriented Community Detection Considering Node Features and Network Topology

Authors:

Guangliang Gao,

Jie CaoAuthors Info & Claims

ACM Transactions on the Web, Volume 18, Issue 1

Article No.: 11, Pages 1 - 21

https://doi.org/10.1145/3626190

Published: 03 November 2023 Publication History

Abstract

The joint use of node features and network topology to detect communities is called community detection in attributed networks. Most of the existing work along this line has been carried out through objective function optimization and has proposed numerous approaches. However, they tend to focus only on lower-order details, i.e., capture node features and network topology from node and edge views, and purely seek a higher degree of optimization to guarantee the quality of the found communities, which exacerbates unbalanced communities and free-rider effect. To further clarify and reveal the intrinsic nature of networks, we conduct triangle-oriented community detection considering node features and network topology. Specifically, we first introduce a triangle-based quality metric to preserve higher-order details of node features and network topology, and then formulate so-called two-level constraints to encode lower-order details of node features and network topology. Finally, we develop a local search framework based on optimizing our objective function consisting of the proposed quality metric and two-level constraints to achieve both non-overlapping and overlapping community detection in attributed networks. Extensive experiments demonstrate the effectiveness and efficiency of our framework and its potential in alleviating unbalanced communities and free-rider effect.

References

[1]

Sanghamitra Bandyopadhyay, Garisha Chowdhary, and Debarka Sengupta. 2015. FOCS: Fast overlapped community search. IEEE Trans. Knowl. Data Eng. 27, 11 (2015), 2974–2985. DOI:

Digital Library

[2]

Austin R. Benson, David F. Gleich, and Jure Leskovec. 2016. Higher-order organization of complex networks. Science 353, 6295 (2016), 163–166.

[3]

Kamal Berahmand, Sogol Haghani, Mehrdad Rostami, and Yuefeng Li. 2022. A new attributed graph clustering by using label propagation in complex networks. J. King Saud Univ. Comput. Info. Sci. 34, 5 (2022), 1869–1883. DOI:

Digital Library

[4]

Zhan Bu, Guangliang Gao, Huijia Li, and Jie Cao. 2017. CAMAS: A cluster-aware multiagent system for attributed graph clustering. Info. Fusion 37 (2017), 10–21. DOI:

Digital Library

[5]

Zhan Bu, Huijia Li, Jie Cao, Zhen Wang, and Guangliang Gao. 2019. Dynamic cluster formation game for attributed graph clustering. IEEE Trans. Cybernet. 49, 1 (2019), 328–341. DOI:

[6]

Tanmoy Chakraborty, Ayushi Dalmia, Animesh Mukherjee, and Niloy Ganguly. 2017. Metrics for community analysis: A survey. Comput. Surveys 50, 4 (2017), 54:1–54:37. DOI:

Digital Library

[7]

Petr Chunaev. 2020. Community detection in node-attributed social networks: A survey. Comput. Sci. Rev. 37 (2020), 100286–100310. DOI:

[8]

Matteo Cinelli, Gianmarco De Francisci Morales, Alessandro Galeazzi, Walter Quattrociocchi, and Michele Starnini. 2021. The echo chamber effect on social media. Proc. Natl. Acad. Sci. U.S.A. 118, 9 (2021), e2023301118:1–8. DOI:

[9]

David Combe, Christine Largeron, Mathias Géry, and Elöd Egyed-Zsigmond. 2015. I-louvain: An attributed graph clustering method. In Proceedings of the 14th International Symposium on Advances in Intelligent Data Analysis (Lecture Notes in Computer Science), Vol. 9385. Springer, 181–192. DOI:

[10]

Kaize Ding, Jundong Li, and Huan Liu. 2019. Interactive anomaly detection on attributed networks. In Proceedings of the 12th International Conference on Web Search and Data Mining. ACM, 357–365. DOI:

Digital Library

[11]

Ernesto Estrada. 2011. Combinatorial study of degree assortativity in networks. Phys. Rev. E 84, 4 (2011), 047101:1–4.

[12]

Issam Falih, Nistor Grozavu, Rushed Kanawati, and Younès Bennani. 2018. Community detection in attributed network. In Proceedings of the Web Conference. 1299–1306.

Digital Library

[13]

Santo Fortunato and Marc Barthelemy. 2007. Resolution limit in community detection. Proc. Natl. Acad. Sci. U.S.A. 104, 1 (2007), 36–41.

[14]

Santo Fortunato and Darko Hric. 2016. Community detection in networks: A user guide. Phys. Rep. 659 (2016), 1–44.

[15]

Santo Fortunato and Mark E. J. Newman. 2022. 20 years of network community detection. Nature Phys. 18, 8 (2022), 848–850.

[16]

Guangliang Gao, Zhiang Wu, Lu Zhang, Jie Cao, and Xinzhe Qi. 2022. Community detection via local learning based on generalized metric with neighboring regularization. IEEE Trans. Syst. Man Cybernet.-Syst. 52, 1 (2022), 498–510. DOI:

[17]

Stephan Günnemann, Brigitte Boden, Ines Färber, and Thomas Seidl. 2013. Efficient mining of combined subspace and subgraph clusters in graphs with feature vectors. In Proceedings of the 17th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining (Lecture Notes in Computer Science), Vol. 7818. Springer, 261–275. DOI:

[18]

Chaobo He, Xiang Fei, Qiwei Cheng, Hanchao Li, Zeng Hu, and Yong Tang. 2022. A survey of community detection in complex networks using nonnegative matrix factorization. IEEE Trans. Comput. Soc. Syst. 9, 2 (2022), 440–457. DOI:

[19]

Alexandre Hollocou, Julien Maudet, Thomas Bonald, and Marc Lelarge. 2017. A linear streaming algorithm for community detection in very large networks. Retrieved from https://arxiv.org/abs/1703.02955.

[20]

Lun Hu, Keith CC Chan, Xiaohui Yuan, and Shengwu Xiong. 2019. A variational Bayesian framework for cluster analysis in a complex network. IEEE Trans. Knowl. Data Eng. 32, 11 (2019), 2115–2128.

[21]

Lun Hu, Xiangyu Pan, Zehai Tang, and Xin Luo. 2021. A fast fuzzy clustering algorithm for complex networks via a generalized momentum method. IEEE Trans. Fuzzy Syst. 30, 9 (2021), 3473–3485.

[22]

Lun Hu, Xiangyu Pan, Hong Yan, Pengwei Hu, and Tiantian He. 2021. Exploiting higher-order patterns for community detection in attributed graphs. Integr. Comput.-Aided Eng. 28, 2 (2021), 207–218. DOI:

[23]

Lun Hu, Jun Zhang, Xiangyu Pan, Hong Yan, and Zhu-Hong You. 2021. HiSCF: Leveraging higher-order structures for clustering analysis in biological networks. Bioinformatics 37, 4 (2021), 542–550.

[24]

Shixun Huang, Yuchen Li, Zhifeng Bao, and Zhao Li. 2021. Towards efficient motif-based graph partitioning: An adaptive sampling approach. In Proceedings of the 37th International Conference on Data Engineering. IEEE, 528–539. DOI:

[25]

Muhammad Aqib Javed, Muhammad Shahzad Younis, Siddique Latif, Junaid Qadir, and Adeel Baig. 2018. Community detection in networks: A multidisciplinary review. J. Netw. Comput. Appl. 108 (2018), 87–111. DOI:

Digital Library

[26]

Caiyan Jia, Yafang Li, Matthew B. Carson, Xiaoyang Wang, and Jian Yu. 2017. Node attribute-enhanced community detection in complex networks. Sci. Rep. 7, 1 (2017), 1–15.

[27]

Di Jin, Zhizhi Yu, Pengfei Jiao, Shirui Pan, Dongxiao He, Jia Wu, Philip S. Yu, and Weixiong Zhang. 2023. A survey of community detection approaches: From statistical modeling to deep learning. IEEE Trans. Knowl. Data Eng. 35, 2 (2023), 1149–1170. DOI:

[28]

Christine Largeron, Pierre-Nicolas Mougel, Reihaneh Rabbany, and Osmar R. Zaïane. 2015. Generating attributed networks with communities. PloS One 10, 4 (2015), e0122777:1–13.

[29]

Pei-Zhen Li, Ling Huang, Chang-Dong Wang, Dong Huang, and Jian-Huang Lai. 2018. Community detection using attribute homogenous motif. IEEE Access 6 (2018), 47707–47716. DOI:

[30]

Pei-Zhen Li, Ling Huang, Chang-Dong Wang, and Jian-Huang Lai. 2019. EdMot: An edge enhancement approach for motif-aware community detection. In Proceedings of the 25th International Conference on Knowledge Discovery and Data Mining. ACM, 479–487. DOI:

Digital Library

[31]

Zhangtao Li, Jing Liu, and Kai Wu. 2018. A multiobjective evolutionary algorithm based on structural and attribute similarities for community detection in attributed networks. IEEE Trans. Cybernet. 48, 7 (2018), 1963–1976. DOI:

[32]

Fanzhen Liu, Zhao Li, Baokun Wang, Jia Wu, Jian Yang, Jiaming Huang, Yiqing Zhang, Weiqiang Wang, Shan Xue, Surya Nepal, and others. 2022. eRiskCom: An e-commerce risky community detection platform. Proc. VLDB Endow. 31, 5 (2022), 1085–1101. DOI:

Digital Library

[33]

Yang Liu, Chen Liang, Xiangnan He, Jiaying Peng, Zibin Zheng, and Jie Tang. 2022. Modelling high-order social relations for item recommendation. IEEE Trans. Knowl. Data Eng. 34, 9 (2022), 4385–4397. DOI:

[34]

Meilian Lu, Zhenglin Zhang, Zhihe Qu, and Yu Kang. 2019. LPANNI: Overlapping community detection using label propagation in large-scale complex networks. IEEE Trans. Knowl. Data Eng. 31, 9 (2019), 1736–1749. DOI:

Digital Library

[35]

Tianshu Lyu, Lidong Bing, Zhao Zhang, and Yan Zhang. 2016. Efficient and scalable detection of overlapping communities in big networks. In Proceedings of the 16th International Conference on Data Mining. IEEE Computer Society, 1071–1076. DOI:

[36]

Seiji Maekawa, Koh Takeuchi, and Makoto Onizuka. 2018. Non-linear attributed graph clustering by symmetric NMF with PU learning. Retrieved from https://arxiv.org/abs/1810.00946.

[37]

Deepanshu Malhotra and Anuradha Chug. 2021. A modified label propagation algorithm for community detection in attributed networks. Int. J. Info. Manage. Data Insights 1, 2 (2021), 100030–100041.

[38]

Xiangmao Meng, Wenkai Li, Xiaoqing Peng, Yaohang Li, and Min Li. 2021. Protein interaction networks: Centrality, modularity, dynamics, and applications. Front. Comput. Sci. 15, 6 (2021), 1–17.

Digital Library

[39]

Vincenzo Moscato, Antonio Picariello, and Giancarlo Sperlì. 2019. Community detection based on game theory. Eng. Appl. Artific. Intell. 85 (2019), 773–782. DOI:

[40]

Mark E. J. Newman. 2006. Modularity and community structure in networks. Proc. Natl. Acad. Sci. U.S.A. 103, 23 (2006), 8577–8582.

[41]

Ashwin Paranjape, Austin R. Benson, and Jure Leskovec. 2017. Motifs in temporal networks. In Proceedings of the 10th International Conference on Web Search and Data Mining. ACM, 601–610. DOI:

Digital Library

[42]

Leto Peel, Daniel B. Larremore, and Aaron Clauset. 2017. The ground truth about metadata and community detection in networks. Sci. Adv. 3, 5 (2017), e1602548:1–8.

[43]

Arnau Prat-Perez, David Dominguez-Sal, and Josep-LLuis Larriba-Pey. 2014. High quality, scalable and parallel community detection for large real graphs. In Proceedings of the 23rd International Conference on World Wide Web. ACM, 225–236. DOI:

Digital Library

[44]

Mohammad Rezaei and Pasi Fränti. 2016. Set matching measures for external cluster validity. IEEE Trans. Knowl. Data Eng. 28, 8 (2016), 2173–2186. DOI:

Digital Library

[45]

Ryan A. Rossi, Nesreen K. Ahmed, and Eunyee Koh. 2018. Higher-order network representation learning. In Proceedings of the Web Conference. ACM, 3–4. DOI:

Digital Library

[46]

Martin Rosvall and Carl T. Bergstrom. 2007. Maps of information flow reveal community structure in complex networks. Retrieved from https://arxiv.org/abs/0707.0609.

[47]

Jianbo Shi and Jitendra Malik. 2000. Normalized cuts and image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 22, 8 (2000), 888–905. DOI:

Digital Library

[48]

Laura M. Smith, Linhong Zhu, Kristina Lerman, and Allon G. Percus. 2016. Partitioning networks with node attributes by compressing information flow. ACM Trans. Knowl. Discov. Data 11, 2 (2016), 15:1–15:26. DOI:

Digital Library

[49]

Konstantinos Sotiropoulos and Charalampos E. Tsourakakis. 2021. Triangle-aware spectral sparsifiers and community detection. In Proceedings of the 27th International Conference on Knowledge Discovery and Data Mining. ACM, 1501–1509. DOI:

Digital Library

[50]

Xing Su, Shan Xue, Fanzhen Liu, Jia Wu, Jian Yang, Chuan Zhou, Wenbin Hu, Cecile Paris, Surya Nepal, Di Jin, and others. 2022. A comprehensive survey on community detection with deep learning. IEEE Trans. Neural Netw. Learn. Syst. (2022), 1–21. DOI:

[51]

Yubao Wu, Ruoming Jin, Jing Li, and Xiang Zhang. 2015. Robust local community detection: On free rider effect and its elimination. Proc. VLDB Endow. 8, 7 (2015), 798–809. DOI:

Digital Library

[52]

Feng Xia, Shuo Yu, Chengfei Liu, Jianxin Li, and Ivan Lee. 2022. Chief: Clustering with higher-order motifs in big networks. IEEE Trans. Netw. Sci. Eng. 9, 3 (2022), 990–1005. DOI:

[53]

Xiaoqin Xie, Mingjie Song, Chiming Liu, Jiaming Zhang, and Jiahui Li. 2021. Effective influential community search on attributed graph. Neurocomputing 444 (2021), 111–125. DOI:

[54]

Xin-Li Xu, Yun-Yue Xiao, Xu-Hua Yang, Lei Wang, and Yan-Bo Zhou. 2022. Attributed network community detection based on network embedding and parameter-free clustering. Appl. Intell. 52, 7 (2022), 8073–8086.

Digital Library

[55]

Zhiqiang Xu, Yiping Ke, Yi Wang, Hong Cheng, and James Cheng. 2012. A model-based approach to attributed graph clustering. In Proceedings of the 31st International Conference on Management of Data. ACM, 505–516. DOI:

Digital Library

[56]

Jaewon Yang and Jure Leskovec. 2013. Overlapping community detection at scale: A nonnegative matrix factorization approach. In Proceedings of the 6th International Conference on Web Search and Data Mining. ACM, 587–596. DOI:

Digital Library

[57]

Jaewon Yang, Julian J. McAuley, and Jure Leskovec. 2013. Community detection in networks with node attributes. In Proceedings of the 13th International Conference on Data Mining. IEEE Computer Society, 1151–1156. DOI:

[58]

Hao Yin, Austin R. Benson, Jure Leskovec, and David F. Gleich. 2017. Local higher-order graph clustering. In Proceedings of the 23rd International Conference on Knowledge Discovery and Data Mining. ACM, 555–564. DOI:

Digital Library

[59]

Chen Zhe, Aixin Sun, and Xiaokui Xiao. 2019. Community detection on large complex attribute network. In Proceedings of the 25th International Conference on Knowledge Discovery and Data Mining. ACM, 2041–2049. DOI:

Digital Library

[60]

Yang Zhou, Hong Cheng, and Jeffrey Xu Yu. 2009. Graph clustering based on structural/attribute similarities. Proc. VLDB Endow. 2, 1 (2009), 718–729. DOI:

Digital Library

Cited By

Puleo JBuchanan AKatenka NHalloran MFriedman SNikolopoulos G(2024)Assessing Spillover Effects of Medications for Opioid Use Disorder on HIV Risk Behaviors among a Network of People Who Inject DrugsStats10.3390/stats70200347:2(549-575)Online publication date: 19-Jun-2024
https://doi.org/10.3390/stats7020034

Index Terms

Triangle-oriented Community Detection Considering Node Features and Network Topology

Recommendations

Balancing topology structure and node attribute in evolutionary multi-objective community detection for attributed networks
Abstract
The task of community detection in attributed networks is to find a good community partition in terms of both topology structure and node attribute. Despite that a number of algorithms have been suggested for community detection in ...
A Simple and Effective Community Detection Method Combining Network Topology with Node Attributes
Knowledge Science, Engineering and Management
Abstract
Community detection is a fundamental problem in the study of complex networks. So far, extensive approaches, which use network topology alone or use both network topology and attribute information, have been designed to detect the community ...
Community detection in subspace of attribute
Abstract
In recent years, attributed networks are increasingly available for us. How to leverage attribute information to gain a better performance of community detection has attracted growing attention. Most established approaches focus on ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on the Web

ACM Transactions on the Web Volume 18, Issue 1

February 2024

448 pages

EISSN:1559-114X

DOI:10.1145/3613532

Editor:
Ryen White
Microsoft Research, USA

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 November 2023

Online AM: 02 October 2023

Accepted: 12 September 2023

Revised: 21 August 2023

Received: 09 November 2022

Published in TWEB Volume 18, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Key Program of National Natural Science Foundation of China
Natural Science Foundation of the Jiangsu Higher Education Institutions of China
Philosophy and Social Foundation of the Jiangsu Higher Education Institutions of China
Key Discipline Construction Project of Cyberspace Security of the 14th Five-Year Plan of Jiangsu Province

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
238
Total Downloads

Downloads (Last 12 months)180
Downloads (Last 6 weeks)17

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Puleo JBuchanan AKatenka NHalloran MFriedman SNikolopoulos G(2024)Assessing Spillover Effects of Medications for Opioid Use Disorder on HIV Risk Behaviors among a Network of People Who Inject DrugsStats10.3390/stats70200347:2(549-575)Online publication date: 19-Jun-2024
https://doi.org/10.3390/stats7020034

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Full Text

View this article in Full Text.

Media

Figures

Other

Tables

View full text|Download PDF

View Issue’s Table of Contents