research-article

MCEIL: An Improved Scoring Function for Overlapping Community Detection using Seed Expansion Methods

Authors:

Prathamesh Deshpande,

Balaraman RavindranAuthors Info & Claims

ASONAM '17: Proceedings of the 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2017

Pages 652 - 659

https://doi.org/10.1145/3110025.3116193

Published: 31 July 2017 Publication History

Abstract

Community detection is one of the most well known problems in complex network analysis. In real-world networks, communities often overlap. Various approaches have been proposed in the literature to detect overlapping communities in networks. Local Expansion and optimization approaches have gained popularity due to their scalability and robustness. In a method based on local expansion, the seeding strategy and scoring function employed are crucial to the performance of the algorithm.

In this paper, a scoring function called CEIL score is used with ground-truth seeds in local expansion and optimization algorithm. Using CEIL score has significantly improved performance of the algorithms with respect to evaluation metrics NMI and F1 score. However, CEIL has lower coverage than conductance. An extension to CEIL score, called MCEIL score is proposed. Using MCEIL score returns communities with coverage as high as conductance, and NMI and F1 scores higher than conductance on different kinds of datasets.

Experiments on datasets of different types with different seeding strategies show that the improvements in NMI and F1 score obtained by MCEIL score are substantial.

References

[1]

G. Palla, I. Derényi, I. Farkas, and T. Vicsek, "Uncovering the overlapping community structure of complex networks in nature and society," Nature, vol. 435, no. 7043, pp. 814--818, 2005.

[2]

Y.-Y. Ahn, J. P. Bagrow, and S. Lehmann, "Link communities reveal multiscale complexity in networks," Nature, vol. 466, no. 7307, pp. 761--764, 2010.

[3]

A. Lancichinetti, S. Fortunato, and J. Kertész, "Detecting the overlapping and hierarchical community structure in complex networks," New Journal of Physics, vol. 11, no. 3, p. 033015, 2009.

[4]

U. N. Raghavan, R. Albert, and S. Kumara, "Near linear time algorithm to detect community structures in large-scale networks," Physical Review E, vol. 76, no. 3, p. 036106, 2007.

[5]

J. Yang and J. Leskovec, "Community-affiliation graph model for overlapping network community detection," in 12th International Conference on Data Mining. IEEE, 2012, pp. 1170--1175.

Digital Library

[6]

J. Yang and J. Leskovec, "Defining and evaluating network communities based on ground-truth," in Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics, ser. MDS '12. New York, NY, USA: ACM, 2012, pp. 3:1--3:8. [Online]. Available: http://doi.acm.org/10.1145/2350190.2350193

[7]

J. J. Whang, D. F. Gleich, and I. S. Dhillon, "Overlapping community detection using neighborhood-inflated seed expansion," IEEE Transactions on Knowledge and Data Engineering, vol. 28, no. 5, pp. 1272--1284, 2016.

Digital Library

[8]

C. Lee, F. Reid, A. McDaid, and N. Hurley, "Detecting highly overlapping community structure by greedy clique expansion," arXiv preprint arXiv:1002.1827, 2010.

[9]

F. Moradi, T. Olovsson, and P. Tsigas, "A local seed selection algorithm for overlapping community detection," in International Conference on Advances in Social Networks Analysis and Mining (ASONAM). IEEE, 2014, pp. 1--8.

[10]

M. V. Sankar, B. Ravindran, and S. Shivashankar, "Ceil: A scalable, resolution limit free approach for detecting communities in large networks," in Proceedings of the 24th International Conference on Artificial Intelligence, ser. IJCAI'15. AAAI Press, 2015, pp. 2097--2103. [Online]. Available: http://dl.acm.org/citation.cfm?id=2832415.2832540

[11]

J. Xie, S. Kelley, and B. K. Szymanski, "Overlapping community detection in networks: The state-of-the-art and comparative study," ACM Computing Surveys (csur), vol. 45, no. 4, p. 43, 2013.

Digital Library

[12]

F. Havemann, M. Heinz, A. Struck, and J. Gläser, "Identification of overlapping communities and their hierarchy by locally calculating community-changing resolution levels," Journal of Statistical Mechanics: Theory and Experiment, vol. 2011, no. 01, p. P01023, 2011.

[13]

T. H. Haveliwala, "Topic-sensitive pagerank," in Proceedings of the 11th International Conference on World Wide Web, ser. WWW '02. New York, NY, USA: ACM, 2002, pp. 517--526. [Online]. Available: http://doi.acm.org/10.1145/511446.511513

Digital Library

[14]

R. Andersen, F. Chung, and K. Lang, "Local graph partitioning using pagerank vectors," in 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06). IEEE, 2006, pp. 475--486.

Digital Library

[15]

D. Hric, R. K. Darst, and S. Fortunato, "Community detection in networks: Structural communities versus ground truth," Physical Review E, vol. 90, no. 6, p. 062805, 2014.

[16]

I. M. Kloumann and J. M. Kleinberg, "Community membership identification from small seed sets," in Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ser. KDD '14. New York, NY, USA: ACM, 2014, pp. 1366--1375. [Online]. Available: http://doi.acm.org/10.1145/2623330.2623621

Digital Library

[17]

B. Abrahao, S. Soundarajan, J. Hopcroft, and R. Kleinberg, "On the separability of structural classes of communities," in Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ser. KDD '12. New York, NY, USA: ACM, 2012, pp. 624--632. [Online]. Available: http://doi.acm.org/10.1145/2339530.2339631

Digital Library

[18]

J. Baumes, M. K. Goldberg, M. S. Krishnamoorthy, M. Magdon-Ismail, and N. Preston, "Finding communities by clustering a graph into overlapping subgraphs." IADIS AC, vol. 5, pp. 97--104, 2005.

[19]

Q. Chen, T.-T. Wu, and M. Fang, "Detecting local community structures in complex networks based on local degree central nodes," Physica A: Statistical Mechanics and its Applications, vol. 392, no. 3, pp. 529--537, 2013. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S0378437112008461

[20]

D. F. Gleich and C. Seshadhri, "Vertex neighborhoods, low conductance cuts, and good seeds for local community methods," in Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ser. KDD '12. New York, NY, USA: ACM, 2012, pp. 597--605. [Online]. Available: http://doi.acm.org/10.1145/2339530.2339628

Digital Library

[21]

J. Yang and J. Leskovec, "Structure and overlaps of ground-truth communities in networks," ACM Trans. Intell. Syst. Technol., vol. 5, no. 2, pp. 26:1--26:35, Apr. 2014. [Online]. Available: http://doi.acm.org/10.1145/2594454

Digital Library

[22]

M. E. Newman, "Fast algorithm for detecting community structure in networks," Physical review E, vol. 69, no. 6, p. 066133, 2004.

Cited By

Lei GSheng YShaozi LQingshou W(2021) Hierarchical community‐discovery algorithm combining core nodes and three‐order structure model Concurrency and Computation: Practice and Experience10.1002/cpe.666934:4Online publication date: 23-Nov-2021
https://doi.org/10.1002/cpe.6669
Li QZhong JLi QWang CCao Z(2019)A Community Merger of Optimization Algorithm to Extract Overlapping Communities in NetworksIEEE Access10.1109/ACCESS.2018.28844477(3994-4005)Online publication date: 2019
https://doi.org/10.1109/ACCESS.2018.2884447
Ma TLiu QCao JTian YAl-Dhelaan AAl-Rodhaan M(2019)LGIEM: Global and local node influence based community detectionFuture Generation Computer Systems10.1016/j.future.2019.12.022Online publication date: Dec-2019
https://doi.org/10.1016/j.future.2019.12.022

MCEIL: An Improved Scoring Function for Overlapping Community Detection using Seed Expansion Methods
1. Human-centered computing
  1. Human computer interaction (HCI)
    1. Interaction paradigms
2. Information systems
  1. Information systems applications

Recommendations

Gauging the Quality of Relevance Assessments using Inter-Rater Agreement
SIGIR '17: Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval

In recent years, gathering relevance judgments through non-topic originators has become an increasingly important problem in Information Retrieval. Relevance judgments can be used to measure the effectiveness of a system, and are often needed to build ...
Are Secondary Assessors Uncertain When They Disagree About Relevance Judgements?
CHIIR '16: Proceedings of the 2016 ACM on Conference on Human Information Interaction and Retrieval

The collection of relevance judgements by assessors is important for many information retrieval (IR) tasks. In addition to the construction of test collections, relevance judging is critical to e-discovery and other applications where many assessors are ...
Investigating the Combined Effects of Rater Expertise, Working Memory Capacity, and Cognitive Functionality on the Scoring of Second Language Speaking Performance

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASONAM '17: Proceedings of the 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2017

July 2017

698 pages

ISBN:9781450349932

DOI:10.1145/3110025

Copyright © 2017 ACM.

© 2017 Association for Computing Machinery. ACM acknowledges that this contribution was authored or co-authored by an employee, contractor or affiliate of a national government. As such, the Government retains a nonexclusive, royalty-free right to publish or reproduce this article, or to allow others to do so, for Government purposes only.

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 31 July 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article
Research
Refereed limited

Conference

ASONAM '17

Sponsor:

SIGKDD

ASONAM '17: Advances in Social Networks Analysis and Mining 2017

July 31 - August 3, 2017

Sydney, Australia

Upcoming Conference

KDD '25

Sponsor:
sigkdd
sigkdd

The 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining

August 3 - 7, 2025

Toronto , ON , Canada

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
116
Total Downloads

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

Reflects downloads up to 23 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Lei GSheng YShaozi LQingshou W(2021) Hierarchical community‐discovery algorithm combining core nodes and three‐order structure model Concurrency and Computation: Practice and Experience10.1002/cpe.666934:4Online publication date: 23-Nov-2021
https://doi.org/10.1002/cpe.6669
Li QZhong JLi QWang CCao Z(2019)A Community Merger of Optimization Algorithm to Extract Overlapping Communities in NetworksIEEE Access10.1109/ACCESS.2018.28844477(3994-4005)Online publication date: 2019
https://doi.org/10.1109/ACCESS.2018.2884447
Ma TLiu QCao JTian YAl-Dhelaan AAl-Rodhaan M(2019)LGIEM: Global and local node influence based community detectionFuture Generation Computer Systems10.1016/j.future.2019.12.022Online publication date: Dec-2019
https://doi.org/10.1016/j.future.2019.12.022

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.

Figures

Tables

Media

View Table of Conten