skip to main content
10.1145/1367497.1367733acmconferencesArticle/Chapter ViewAbstractPublication PagesthewebconfConference Proceedingsconference-collections
poster

A framework for fast community extraction of large-scale networks

Published: 21 April 2008 Publication History

Abstract

Most of the faster community extraction algorithms are based on the Clauset, Newman and Moore (CNM), which is employed for networks with sizes up to 500,000 nodes. The modification proposed by Danon, Diaz and Arenas (DDA) obtains better modularity among CNM and its variations, but there is no improvement in speed as its authors expressed. In this paper, we identify some inefficiencies in the data structure employed by former algorithms. We propose a new framework for the algorithm and a modification of the DDA to make it applicable to large-scale networks. For instance, the community extraction of a network with 1 million nodes and 5 million edges was performed in about 14 minutes in contrast to former CNM that required 45 hours (192 times the former CNM, obtaining better modularity).
The scalability of our improvements is shown by applying it to networks with sizes up to 10 million nodes, obtaining the best modularity and execution time compared to the former algorithms.

References

[1]
Clauset, M. E. J. Newman, and C. Moore. Finding community structure in very large networks. PRE, 70:066111, 2004.
[2]
Danon, A. Diaz-Guilera, and A. Arenas. Effect of size heterogeneity on community identification in complex networks. Stat. Mech., P11010, 2006.
[3]
Wakita and T. Tsurumi. Finding community structure in mega-scale social networks. arXiv:cs/0702048, 2007.
[4]
Yuta, N. Ono, and Y. Fujiwara. A gap in the community-size distribution of a large-scale social networking site. arXiv:physics/0701168v2, 2007.

Cited By

View all
  • (2014)Clique guided community detection2014 IEEE International Conference on Big Data (Big Data)10.1109/BigData.2014.7004267(500-509)Online publication date: Oct-2014
  • (2010)Framework for Fast Identification of Community Structures in Large-Scale Social NetworksData Mining for Social Network Data10.1007/978-1-4419-6287-4_9(149-175)Online publication date: 20-May-2010
  • (2009)Mining communities in networksProceedings of the 9th ACM SIGCOMM conference on Internet measurement10.1145/1644893.1644930(301-314)Online publication date: 4-Nov-2009
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
WWW '08: Proceedings of the 17th international conference on World Wide Web
April 2008
1326 pages
ISBN:9781605580852
DOI:10.1145/1367497
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 ACM 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

In-Cooperation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 April 2008

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. clustering
  2. community analysis
  3. large-scale networks

Qualifiers

  • Poster

Conference

WWW '08
Sponsor:

Acceptance Rates

Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)3
  • Downloads (Last 6 weeks)0
Reflects downloads up to 17 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2014)Clique guided community detection2014 IEEE International Conference on Big Data (Big Data)10.1109/BigData.2014.7004267(500-509)Online publication date: Oct-2014
  • (2010)Framework for Fast Identification of Community Structures in Large-Scale Social NetworksData Mining for Social Network Data10.1007/978-1-4419-6287-4_9(149-175)Online publication date: 20-May-2010
  • (2009)Mining communities in networksProceedings of the 9th ACM SIGCOMM conference on Internet measurement10.1145/1644893.1644930(301-314)Online publication date: 4-Nov-2009
  • (2009)Effective Criterion Functions for Efficient Agglomerative Clustering on Very Large NetworksProceedings of the 2009 Ninth IEEE International Conference on Data Mining10.1109/ICDM.2009.91(1040-1045)Online publication date: 6-Dec-2009

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media