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

research-article

Robust Dynamic Clustering for Temporal Networks

Authors:

Hidetaka Kamigaito,

Kotaro Funakoshi,

Manabu OkumuraAuthors Info & Claims

CIKM '21: Proceedings of the 30th ACM International Conference on Information & Knowledge Management

Pages 2424 - 2433

https://doi.org/10.1145/3459637.3482473

Published: 30 October 2021 Publication History

Abstract

Dynamic community detection (or graph clustering) in temporal networks has attracted much attention because it is promising for revealing the underlying mechanism of complex real-world systems. Current methods are criticized for the independence of graph representation learning and graph clustering, considerable noise during temporal information smoothing, and high time complexity. We propose a R obust T emporal S moothing C lustering method (RTSC), which involves joint graph representation learning and graph clustering, to solve these problems. RTSC can be formulated as a constrained multi-objective optimization problem. Specifically, three-order successive snapshots are first projected into the same subspace via graph embedding. We then use the embedding matrices to learn a common low-rank block-diagonal matrix that contains current clustering information and specific noise matrices with a sparse constraint to remove noise at each time step. To efficiently solve the challenging optimization problem, we also propose an optimization procedure based on the augmented Lagrangian multiplier (ALM) scheme. Experimental results on six artificial datasets and four real-world dynamic network datasets indicate that RTSC performs better than six state-of-the-art algorithms for dynamic clustering in temporal networks.

Supplementary Material

MP4 File (CIKM21-fp1415.mp4)

Presentation video of "Robust Temporal Smoothing Clustering Approaches"

Download
661.15 MB

References

[1]

Zhan Bu, Huijia Li, Chengcui Zhang, Jie Cao, Aihua Li, and Yong Shi. 2019. Graph K-means based on leader identification, dynamic game, and opinion dynamics. IEEE Transactions on Knowledge and Data Engineering 32, 7 (2019), 1348--1361.

[2]

Jianfeng Cai, Emmanuel J. Candès, and Zuowei Shen. 2010. A Singular Value Thresholding Algorithm for Matrix Completion. SIAM J. Optim. 20, 4 (2010), 1956--1982.

[3]

Deepayan Chakrabarti, Ravi Kumar, and Andrew Tomkins. 2006. Evolutionary clustering. In Proceedings of the Twelfth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, Philadelphia, PA, USA, 554--560.

Digital Library

[4]

Lu Chen, Chengfei Liu, Rui Zhou, Jiajie Xu, Jeffrey Xu Yu, and Jianxin Li. 2020. Finding Effective Geo-social Group for Impromptu Activities with Diverse De- mands. In KDD '20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. ACM, Virtual Event, CA, USA, 698--708.

Digital Library

[5]

Fan RK Chung and Fan Chung Graham. 1997. Spectral graph theory. Number 92 in CBMS Regional Conference Series in Mathematics. American Mathematical Soc., Fresno State University.

[6]

Leon Danon, Albert Díaz-Guilera, Jordi Duch, and Alex Arenas. 2005. Comparing community structure identification. Journal of Statistical Mechanics: Theory and Experiment 2005, 09 (sep 2005), P09008--P09008.

[7]

Lun Du, Yun Wang, Guojie Song, Zhicong Lu, and Junshan Wang. 2018. Dynamic Network Embedding : An Extended Approach for Skip-gram based Network Embedding. In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence. IJCAI Press, Stockholm, Sweden, 2086--2092.

Digital Library

[8]

John C. Duchi, Shai Shalev-Shwartz, Yoram Singer, and Tushar Chandra. 2008. Efficient projections onto the l1-ball for learning in high dimensions. In Machine Learning, Proceedings of the Twenty-Fifth International Conference (ACM Interna- tional Conference Proceeding Series, Vol. 307). ACM, Helsinki, Finland, 272--279.

Digital Library

[9]

Francesco Folino and Clara Pizzuti. 2014. An Evolutionary Multiobjective Ap- proach for Community Discovery in Dynamic Networks. IEEE Trans. Knowl. Data Eng. 26, 8 (2014), 1838--1852.

[10]

Dongqi Fu, Dawei Zhou, and Jingrui He. 2020. Local Motif Clustering o Time- Evolving Graphs. In Conference on Knowledge Discovery and Data Mining. ACM, CA, USA, 390--400.

Digital Library

[11]

Michael Gao, Lindsay Popowski, and Jim Boerkoel. 2020. Dynamic Control of Probabilistic Simple Temporal Networks. In The Thirty-Fourth AAAI Conference on Artificial Intelligence. AAAI Press, New York, NY, USA, 9851--9858.

[12]

Aditya Grover and Jure Leskovec. 2016. node2vec: Scalable Feature Learning for Networks. In Proceedings of the 22nd ACM SIGKDD. ACM, CA, USA, 855--864.

Digital Library

[13]

Benjamin D. Haeffele and René Vidal. 2020. Structured Low-Rank Matrix Fac- torization: Global Optimality, Algorithms, and Applications. IEEE Trans. Pattern Anal. Mach. Intell. 42, 6 (2020), 1468--1482.

[14]

Dongxiao He, Yue Song, Di Jin, Zhiyong Feng, Binbin Zhang, Zhizhi Yu, and Weixiong Zhang. 2020. Community-Centric Graph Convolutional Network for Unsupervised Community Detection. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence. IJCAI Press, Yokohama, Japan, 3515--3521.

[15]

Patrik O Hoyer. 2004. Non-negative matrix factorization with sparseness con- straints. Journal of machine learning research 5, 9 (2004), 1--4.

Digital Library

[16]

Ling Huang, Hong-Yang Chao, and Guangqiang Xie. 2020. MuMod: A Micro-Unit Connection Approach for Hybrid-Order Community Detection. In The Thirty- Fourth AAAI Conference on Artificial Intelligence. AAAI Press, New York, NY, 107--114.

[17]

Di Jin, Kunzeng Wang, Ge Zhang, Pengfei Jiao, Dongxiao He, Francoise Fogelman- Soulie, and Xin Huang. 2019. Detecting Communities with Multiplex Semantics by Distinguishing Background, General, and Specialized Topics. IEEE Transactions on Knowledge and Data Engineering 32, 11 (2019), 2144--2158.

[18]

MinSoo Kim and Jiawei Han. 2009. A Particle-and-Density Based Evolutionary Clustering Method for Dynamic Networks. Proc. VLDB Endow. 2, 1 (2009), 622-- 633.

Digital Library

[19]

Keigo Kimura, Yuzuru Tanaka, and Mineichi Kudo. 2014. A Fast Hierarchical Alternating Least Squares Algorithm for Orthogonal Nonnegative Matrix Fac- torization. In Proceedings of the Sixth Asian Conference on Machine Learning (JMLR Workshop and Conference Proceedings, Vol. 39). JMLR.org, Nha Trang City, Vietnam, 129--141.

[20]

Daniel D Lee and H Sebastian Seung. 1999. Learning the parts of objects by non-negative matrix factorization. Nature 401, 6755 (1999), 788--791.

[21]

Omer Levy and Yoav Goldberg. 2014. Neural Word Embedding as Implicit Matrix Factorization. In Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems. NeurIPS, Montreal, Quebec, Canada, 2177--2185.

Digital Library

[22]

Ye Li, Chaofeng Sha, Xin Huang, and Yanchun Zhang. 2018. Community Detection in Attributed Graphs: An Embedding Approach. In Proceedings of the Thirty- Second AAAI Conference on Artificial Intelligence. AAAI Press, New Orleans, Louisiana, USA, 338--345.

[23]

Fuchen Liu, David Choi, Lu Xie, and Kathryn Roeder. 2018. Global spectral clustering in dynamic networks. Proc Natl Acad Sci 115, 5 (2018), 927--932.

[24]

Fan Liu and Yong Deng. 2021. Determine the Number of Unknown Targets in Open World Based on Elbow Method. IEEE Trans. Fuzzy Syst. 29, 5 (2021), 986--995.

[25]

Fanzhen Liu, Jia Wu, Shan Xue, Chuan Zhou, Jian Yang, and Quanzheng Sheng. 2020. Detecting the evolving community structure in dynamic social networks. World Wide Web 23, 2 (2020), 715--733.

[26]

Xiaoke Ma and Di Dong. 2017. Evolutionary Nonnegative Matrix Factorization Algorithms for Community Detection in Dynamic Networks. IEEE Transactions on Knowledge and Data Engineering 29, 5 (2017), 1045--1058.

Digital Library

[27]

Feiping Nie, Xiaoqian Wang, Cheng Deng, and Heng Huang. 2017. Learning A Structured Optimal Bipartite Graph for Co-Clustering. In Advances in Neural Information Processing Systems 30. NeurIPS, Long Beach, CA, USA, 4129--4138.

Digital Library

[28]

Feiping Nie, Han Zhang, Rong Wang, and Xuelong Li. 2020. Semi-supervised Clustering via Pairwise Constrained Optimal Graph. In Proceedings of the Twenty- Ninth International Joint Conference on Artificial Intelligence. ijcai.org, Yokohama, Japan, 3160--3166.

[29]

Leto Peel and Aaron Clauset. 2015. Detecting Change Points in the Large- Scale Structure of Evolving Networks. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence. AAAI Press, Austin, TexasUSA, 2914--2920.

Digital Library

[30]

Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. 2014. DeepWalk: online learning of social representations. In The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, New York, NY, USA, 701--710.

Digital Library

[31]

Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Jie Tang. 2018. Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec. In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining. ACM, Marina Del Rey, CA, USA, 459--467.

Digital Library

[32]

Peter H Schönemann. 1966. A generalized solution of the orthogonal procrustes problem. Psychometrika 31, 1 (1966), 1--10.

[33]

Jimeng Sun, Christos Faloutsos, Spiros Papadimitriou, and Philip S. Yu. 2007. GraphScope: parameter-free mining of large time-evolving graphs. In Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, California, USA, 687--696.

Digital Library

[34]

Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. 2015. LINE: Large-scale Information Network Embedding. In Proceedings of the 24th International Conference on World Wide Web. ACM, Florence, Italy, 1067--1077.

Digital Library

[35]

Wenjing Wang and Xiang Li. 2020. Temporal Stable Community in Time-Varying Networks. IEEE Trans. Netw. Sci. Eng. 7, 3 (2020), 1508--1520.

[36]

Zhixiao Wang, Zechao Li, Guan Yuan, Yunlian Sun, Xiaobin Rui, and Xinguang Xiang. 2018. Tracking the evolution of overlapping communities in dynamic social networks. Knowl. Based Syst. 157 (2018), 81--97.

[37]

Haozhe Wu, Zhiyuan Hu, Jia Jia, Yaohua Bu, Xiangnan He, and Tat-Seng Chua. 2020. Mining Unfollow Behavior in Large-Scale Online Social Networks via Spatial-Temporal Interaction. In The Thirty-Fourth AAAI Conference on Artificial Intelligence. AAAI, New York, NY, USA, 254--261.

[38]

Rongkai Xia, Yan Pan, Lei Du, and Jian Yin. 2014. Robust Multi-View Spec- tral Clustering via Low-Rank and Sparse Decomposition. In Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence. AAAI Press, Québec City, Québec, Canada, 2149--2155.

Digital Library

[39]

Liang Yang, Xiaochun Cao, Dongxiao He, Chuan Wang, Xiao Wang, and Weixiong Zhang. 2016. Modularity Based Community Detection with Deep Learning. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. IJCAI Press, New York, NY, USA, 2252--2258.

Digital Library

[40]

Jingyi You, Chenlong Hu, Hidetaka Kamigaito, Hiroya Takamura, and Manabu Okumura. 2021. Abstractive Document Summarization with Word Embedding Reconstruction. In Proceedings of the International Conference on Recent Advances in Natural Language Processing. Online, 1--11.

[41]

Xiangxiang Zeng, Wen Wang, Cong Chen, and Gary G. Yen. 2020. A Consen- sus Community-Based Particle Swarm Optimization for Dynamic Community Detection. IEEE Trans. Cybern. 50, 6 (2020), 2502--2513.

[42]

Daokun Zhang, Jie Yin, Xingquan Zhu, and Chengqi Zhang. 2020. Network Representation Learning: A Survey. IEEE Trans. Big Data 6, 1 (2020), 3--28.

[43]

Jingran Zhang, Fumin Shen, Xing Xu, and Heng Tao Shen. 2020. Temporal Reasoning Graph for Activity Recognition. IEEE Trans. Image Process. 29 (2020), 5491--5506.

[44]

Jianlei Zhang, Yuying Zhu, and Zengqiang Chen. 2020. Evolutionary game dynam- ics of multiagent systems on multiple community networks. IEEE Transactions on Systems, Man, and Cybernetics: Systems 50, 11 (2020), 4513--4529.

[45]

Ying Zhao and George Karypis. 2004. Empirical and theoretical comparisons of selected criterion functions for document clustering. Machine Learning 55, 3 (2004), 311--331.

Digital Library

[46]

Linhong Zhu, Dong Guo, Junming Yin, Greg Ver Steeg, and Aram Galstyan. 2017. Scalable Temporal Latent Space Inference for Link Prediction in Dynamic Social Networks. In 33rd IEEE International Conference on Data Engineering. IEEE Computer Society, San Diego, CA, USA, 57--58.

[47]

Di Zhuang, J. Morris Chang, and Mingchen Li. 2021. DynaMo: Dynamic Com- munity Detection by Incrementally Maximizing Modularity. IEEE Trans. Knowl. Data Eng. 33, 5 (2021), 1934--1945.

Cited By

Ai YXie XMa X(2024)Graph Contrastive Learning for Tracking Dynamic Communities in Temporal NetworksIEEE Transactions on Emerging Topics in Computational Intelligence10.1109/TETCI.2024.33868448:5(3422-3435)Online publication date: Oct-2024
https://doi.org/10.1109/TETCI.2024.3386844
Zhang JWang SSun YPeng Z(2023)Prerequisite-driven Fair Clustering on Heterogeneous Information NetworksProceedings of the ACM on Management of Data10.1145/35892671:2(1-27)Online publication date: 20-Jun-2023
https://doi.org/10.1145/3589267
Myers AMuñoz DKhasawneh FMunch E(2023)Temporal network analysis using zigzag persistenceEPJ Data Science10.1140/epjds/s13688-023-00379-512:1Online publication date: 2-Mar-2023
https://doi.org/10.1140/epjds/s13688-023-00379-5

Index Terms

Robust Dynamic Clustering for Temporal Networks

Recommendations

Multi-view Clustering with Graph Embedding for Connectome Analysis
CIKM '17: Proceedings of the 2017 ACM on Conference on Information and Knowledge Management

Multi-view clustering has become a widely studied problem in the area of unsupervised learning. It aims to integrate multiple views by taking advantages of the consensus and complimentary information from multiple views. Most of the existing works in ...
New Clustering Techniques of Node Embeddings Based on Metaheuristic Optimization Algorithms
Large-Scale Scientific Computing
Abstract
Node embeddings present a powerful method of embedding graph-structured data into a low dimensional space while preserving local node information. Clustering is a common preprocessing task on unsupervised data utilized to get the best insight into ...
Evolutionary clustering via graph regularized nonnegative matrix factorization for exploring temporal networks
Abstract
Evolutionary clustering is a classic and helpful framework for modeling dynamic data and has been devoted to analyzing the temporal networks recently. However, all methods based on evolutionary clustering either does not directly model ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CIKM '21: Proceedings of the 30th ACM International Conference on Information & Knowledge Management

October 2021

4966 pages

ISBN:9781450384469

DOI:10.1145/3459637

General Chairs:
Gianluca Demartini
The University of Queensland, Australia
,
Guido Zuccon
The University of Queensland, Australia
,
Program Chairs:
J. Shane Culpepper
RMIT University, Australia
,
Zi Huang
The University of Queensland, Australia
,
Hanghang Tong
University of Illinois at Urbana-Champaign, USA

Copyright © 2021 ACM.

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].

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 October 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

China Scholarship Council

Conference

CIKM '21

Sponsor:

CIKM '21: The 30th ACM International Conference on Information and Knowledge Management

November 1 - 5, 2021

Queensland, Virtual Event, Australia

Acceptance Rates

Overall Acceptance Rate 1,861 of 8,427 submissions, 22%

Upcoming Conference

CIKM '25

Sponsor:
sigir
sigir

The 34th ACM International Conference on Information and Knowledge Management

November 10 - 14, 2025

Seoul , Republic of Korea

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
398
Total Downloads

Downloads (Last 12 months)71
Downloads (Last 6 weeks)12

Reflects downloads up to 17 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ai YXie XMa X(2024)Graph Contrastive Learning for Tracking Dynamic Communities in Temporal NetworksIEEE Transactions on Emerging Topics in Computational Intelligence10.1109/TETCI.2024.33868448:5(3422-3435)Online publication date: Oct-2024
https://doi.org/10.1109/TETCI.2024.3386844
Zhang JWang SSun YPeng Z(2023)Prerequisite-driven Fair Clustering on Heterogeneous Information NetworksProceedings of the ACM on Management of Data10.1145/35892671:2(1-27)Online publication date: 20-Jun-2023
https://doi.org/10.1145/3589267
Myers AMuñoz DKhasawneh FMunch E(2023)Temporal network analysis using zigzag persistenceEPJ Data Science10.1140/epjds/s13688-023-00379-512:1Online publication date: 2-Mar-2023
https://doi.org/10.1140/epjds/s13688-023-00379-5

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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents