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

Article

Fast algorithm for modularity-based graph clustering

Authors:

Hiroaki Shiokawa,

Yasuhiro Fujiwara,

Makoto OnizukaAuthors Info & Claims

AAAI'13: Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence

Pages 1170 - 1176

Published: 14 July 2013 Publication History

Abstract

In AI and Web communities, modularity-based graph clustering algorithms are being applied to various applications. However, existing algorithms are not applied to large graphs because they have to scan all vertices/edges iteratively. The goal of this paper is to efficiently compute clusters with high modularity from extremely large graphs with more than a few billion edges. The heart of our solution is to compute clusters by incrementally pruning unnecessary vertices/edges and optimizing the order of vertex selections. Our experiments show that our proposal outperforms all other modularity-based algorithms in terms of computation time, and it finds clusters with high modularity.

References

[1]

Blei, D. M.; Ng, A. Y.; and Jordan, M. I. 2001. Latent Dirichlet Allocation. In Proceedings of Advances in Neural Information Processing Systems 15 [Neural Information Processing Systems (NIPS 2001)], 601-608. MIT Press.

[2]

Blondel, V. D.; Guillaume, J.-L.; Lambiotte, R.; and Lefebvre, E. 2008. Fast Unfolding of Communities in Large Networks. Journal of Statistical Mechanics: Theory and Experiment 2008:P10008.

[3]

Boldi, P.; Rosa, M.; Santini, M.; and Vigna, S. 2011. Layered Label Propagation: A MultiResolution Coordinate-Free Ordering for Compressing Social Networks. In Proceedings of the 20th international conference on World Wide Web (WWW 2011). ACM Press.

[4]

Browet, A.; Absil, P.-A.; and Dooren, P. V. 2011. Community Detection for Hierarchical Image Segmentation. In Proceedings of the 14th International Workshop on Combinatorial Image Analysis (IWCIA 2011), Lecture Notes in Computer Science, 358-371. Springer.

[5]

Clauset, A.; Newman, M. E. J.; and Moore, C. 2004. Finding Community Structure in Very Large Networks. Physical Review E- PHYS REV E 70:066111.

[6]

Faloutsos, M.; Faloutsos, P.; and Faloutsos, C. 1999. On Power-law Relationships of the Internet Topology. In Proceedings of the ACM SIGCOMM 1999 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication (SIGCOMM 1999), 251-262. New York, NY, USA: ACM.

[7]

Fujiwara, Y.; Nakatsuji, M.; Yamamuro, T.; Shiokawa, H.; and Onizuka, M. 2012. Efficient Personalized PageRank with Accuracy Assurance. In Proceedings of 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2012), 15-23. ACM.

[8]

Herlocker, J. L.; Konstan, J. A.; Borchers, A.; and Riedl, J. 1999. An Algorithmic Framework for Performing Collaborative Filtering. In Proceedings of the 22nd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR 1999), 230-237. ACM.

[9]

Hofmann, T. 2004. Latent Semantic Models for Collaborative Filtering. ACM Transactions on Information Systems (TOIS) 22(1):89-115.

[10]

Kernighan, B. W., and Lin, S. 1970. An Efficient Heuristic Procedure for Partitioning Graphs. Bell System Technical journal 49(2):291-307.

[11]

Kleinberg, J. M. 2002. Bursty and Hierarchical Structure in Streams. In Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2002), 91-101. ACM.

[12]

Latapy, M.; Magnien, C.; and Vecchio, N. D. 2008. Basic Notions for the Analysis of Large Two-mode Networks. Social Networks 30(1):31-48.

[13]

Nakatsuji, M.; Fujiwara, Y.; Uchiyama, T.; and Toda, H. 2012. Collaborative Filtering by Analyzing Dynamic User Interests Modeled by Taxonomy. In Proceedings of the 11th International Semantic Web Conference (ISWC 2012), Lecture Notes in Computer Science, 361-377. Springer.

[14]

Newman, M. E. J., and Girvan, M. 2004. Finding and Evaluating Community Structure in Networks. Physical Review E- PHYS REV E 69:026113.

[15]

Newman, M. E. J. 2003. The Structure and Function of Complex Networks. SIAM REVIEW 45(2):167-256.

[16]

Newman, M. E. J. 2004. Fast Algorithm for Detecting Community Structure in Networks. Physical Review E- PHYS REV E 69:066133.

[17]

Sibona, C., and Choi, J. H. 2012. Factors Affecting End-User Satisfaction on Facebook. In Proceedings of the 6th International AAAI Conference on Weblogs and Social Media (ICWSM 2012). AAAI Press.

[18]

Wakita, K., and Tsurumi, T. 2007. Finding Community Structure in Mega-Scale Social Networks. In Proceedings of the 16th International Conference on World Wide Web (WWW 2007), 1275-1276. ACM.

[19]

Weng, J., and Lee, B.-S. 2011. Event Detection in Twitter. In Proceedings of the 5th International AAAI Conference on Weblogs and Social Media (ICWSM 2011). AAAI Press.

[20]

Yang, Y.; Pierce, T.; and Carbonell, J. G. 1998. A Study of Retrospective and On-Line Event Detection. In Proceedings of the 21st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR 1998), 28-36. ACM.

[21]

Yu, D.; Wu, T.; Shan, Y.; Wang, Y.; He, Y.; and Yang, N. 2010. Making Human Connectome Faster: CPU Acceleration of Brain Network Analysis. In Proceedings of IEEE 16th International Conference on Parallel and Distributed Systems (ICPADS 2010), 593-600. IEEE.

[22]

Zhou, T. C.; Ma, H.; Kyu, M. R.; and King, I. 2010. User-Rec: A User Recommendation Framework in Social Tagging Systems. In Proceedings of the 24th AAAI Conference on Artificial Intelligence (AAAI 2010). AAAI Press.

Cited By

Chen ZSun AXiao X(2021)Incremental Community Detection on Large Complex Attributed NetworkACM Transactions on Knowledge Discovery from Data10.1145/345121615:6(1-20)Online publication date: 19-May-2021
https://dl.acm.org/doi/10.1145/3451216
Schmeißer SSchiele G(2020)coSenseACM/IMS Transactions on Data Science10.1145/33952331:4(1-21)Online publication date: 25-Nov-2020
https://dl.acm.org/doi/10.1145/3395233
Shiokawa HAmagasa TKitagawa H(2019)Scaling fine-grained modularity clustering for massive graphsProceedings of the 28th International Joint Conference on Artificial Intelligence10.5555/3367471.3367682(4597-4604)Online publication date: 10-Aug-2019
https://dl.acm.org/doi/10.5555/3367471.3367682
Show More Cited By

Fast algorithm for modularity-based graph clustering
1. Computing methodologies
  1. Machine learning
    1. Learning paradigms
      1. Unsupervised learning
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

Recommendations

Hybrid Bisect K-Means Clustering Algorithm
BCGIN '11: Proceedings of the 2011 International Conference on Business Computing and Global Informatization

In this paper, we present a hybrid clustering algorithm that combines divisive and agglomerative hierarchical clustering algorithm. Our method uses bisect K-means for divisive clustering algorithm and Unweighted Pair Group Method with Arithmetic Mean (...
A partitional clustering algorithm validated by a clustering tendency index based on graph theory

Applying graph theory to clustering, we propose a partitional clustering method and a clustering tendency index. No initial assumptions about the data set are requested by the method. The number of clusters and the partition that best fits the data set, ...
A fast kernel-based multilevel algorithm for graph clustering
KDD '05: Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining

Graph clustering (also called graph partitioning) --- clustering the nodes of a graph --- is an important problem in diverse data mining applications. Traditional approaches involve optimization of graph clustering objectives such as normalized cut or ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

AAAI'13: Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence

July 2013

1687 pages

Publisher

AAAI Press

Publication History

Published: 14 July 2013

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chen ZSun AXiao X(2021)Incremental Community Detection on Large Complex Attributed NetworkACM Transactions on Knowledge Discovery from Data10.1145/345121615:6(1-20)Online publication date: 19-May-2021
https://dl.acm.org/doi/10.1145/3451216
Schmeißer SSchiele G(2020)coSenseACM/IMS Transactions on Data Science10.1145/33952331:4(1-21)Online publication date: 25-Nov-2020
https://dl.acm.org/doi/10.1145/3395233
Shiokawa HAmagasa TKitagawa H(2019)Scaling fine-grained modularity clustering for massive graphsProceedings of the 28th International Joint Conference on Artificial Intelligence10.5555/3367471.3367682(4597-4604)Online publication date: 10-Aug-2019
https://dl.acm.org/doi/10.5555/3367471.3367682
Yamazaki KMatsugu SShiokawa HKitagawa H(2019)Fast RankCIus Algorithm via Dynamic Rank Score Tracking on Bi-type Information NetworksProceedings of the 21st International Conference on Information Integration and Web-based Applications & Services10.1145/3366030.3366051(110-117)Online publication date: 2-Dec-2019
https://dl.acm.org/doi/10.1145/3366030.3366051
Matsugu SShiokawa HKitagawa H(2019)Flexible Community Search Algorithm on Attributed GraphsProceedings of the 21st International Conference on Information Integration and Web-based Applications & Services10.1145/3366030.3366049(103-109)Online publication date: 2-Dec-2019
https://dl.acm.org/doi/10.1145/3366030.3366049
Zhe CSun AXiao XTeredesai AKumar VLi YRosales RTerzi EKarypis G(2019)Community Detection on Large Complex Attribute NetworkProceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining10.1145/3292500.3330721(2041-2049)Online publication date: 25-Jul-2019
https://dl.acm.org/doi/10.1145/3292500.3330721
Fogaça MKahng AReis RWang LShibuya T(2019)Finding placement-relevant clusters with fast modularity-based clusteringProceedings of the 24th Asia and South Pacific Design Automation Conference10.1145/3287624.3287676(569-576)Online publication date: 21-Jan-2019
https://dl.acm.org/doi/10.1145/3287624.3287676
Shiokawa HFutamura Y(2018)Graph Clustering via Cohesiveness-aware Vector PartitioningProceedings of the 20th International Conference on Information Integration and Web-based Applications & Services10.1145/3282373.3282387(33-40)Online publication date: 19-Nov-2018
https://dl.acm.org/doi/10.1145/3282373.3282387
Matsushita TShiokawa HKitagawa H(2018)C-APProceedings of the 20th International Conference on Information Integration and Web-based Applications & Services10.1145/3282373.3282377(156-163)Online publication date: 19-Nov-2018
https://dl.acm.org/doi/10.1145/3282373.3282377
Yamazaki KSato TShiokawa HKitagawa H(2018)Fast Algorithm for Integrating Clustering with Ranking on Heterogeneous GraphsProceedings of the 20th International Conference on Information Integration and Web-based Applications & Services10.1145/3282373.3282376(24-32)Online publication date: 19-Nov-2018
https://dl.acm.org/doi/10.1145/3282373.3282376
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents