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

research-article

A density-based approach for mining overlapping communities from social network interactions

Authors:

Sajid Yousuf Bhat,

Muhammad AbulaishAuthors Info & Claims

WIMS '12: Proceedings of the 2nd International Conference on Web Intelligence, Mining and Semantics

Article No.: 9, Pages 1 - 7

https://doi.org/10.1145/2254129.2254143

Published: 13 June 2012 Publication History

Abstract

In this paper, we propose a density-based community detection method, CMiner, which exploits the interaction graph of online social networks to identify overlapping community structures. Based on the average reciprocated interactions of a node in the network, a new distance function is defined to find the similarity between a pair of nodes. The proposed method also provides a basic solution for automatic determination of the neighborhood threshold, which is a non-trivial problem for applying density-based clustering methods. Considering the local neighborhood of a node p, the distance function is used to determine the distance between the node p and its neighbors in the interaction graph to identify core nodes, which are then used to define overlapping communities. On comparing the experimental results with clique percolation and other related methods, we found that CMiner is comparable to the state-of-the-art methods and is also computationally faster.

References

[1]

G. Agarwal and D. Kempe. Modularity maximizing network communities using mathematical programming. The European Physical Journal B, 66:409--418, 2008.

[2]

H. Chun, H. Kwak, Y. Eom, Y. Ahn, S. Moon, and H. Jeong. Comparison of online social relations in volume vs interaction: a case study of cyworld. In Proceedings of the 8th ACM SIGCOMM Conference on Internet Measurement, volume 5247, pages 57--70, 2008.

Digital Library

[3]

A. Clauset. Finding local community structure in networks. Physical Review E, 72:026132, 2005.

[4]

A. Clauset, C. Moore, and M. E. Newman. Hierarchical structure and the prediction of missing links in networks. Nature, 453(7191):98--101, 2008.

[5]

A. Clauset, M. E. Newman, and C. Moore. Finding community structure in very large networks. Physical Review E, 70:066111, 2004.

[6]

C. H. Ding, X. He, H. Zha, M. Gu, and H. D. Simon. A min-max cut algorithm for graph partitioning. In Proceedings of the International Conference on Data Mining, pages 107--114, 2001.

Digital Library

[7]

M. Ester, H. Kriegel, S. Jörg, and X. Xu. A density-based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of the International Conference on Knowledge Discovery from Data, pages 226--231, 1996.

[8]

T. Falkowski, A. Barth, and M. Spiliopoulou. DENGRAPH: a density-based community detection algorithm. In Proceedings of the IEEE/WIC/ACM International Conference on Web Intelligence, pages 112--115. IEEE Computer Society, Washington, DC, USA, 2007.

Digital Library

[9]

S. Fortunato. Community detection in graphs. Physics Reports, 486(3--5):75--174, 2010.

[10]

S. Fortunato and M. Barthélemy. Resolution limit in community detection. In Proceedings of the National Academy of Science, volume 104, pages 36--41, 2007.

[11]

M. Girvan and M. E. Newman. Community structure in social and biological networks. In Proceedings of the National Academy of Sciences, volume 99, pages 7821--7826, 2002.

[12]

S. Gregory. An algorithm to find overlapping community structure in networks. In Proceedings of the 11th European Conference on Principles and Practice of Knowledge Discovery in Databases, pages 91--102, 2007.

Digital Library

[13]

M. S. Handcock, A. E. Rafter, and J. M. Tantrum. Model-based clustering for social networks. Journal of the Royal Statistical Society A, 170:301--354, 2007.

[14]

B. W. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. Bell System Technical Journal, 49:291--307, 1970.

[15]

A. Lancichinetti and S. Fortunato. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities. Physical Review E, 80:016118, 2009.

[16]

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

[17]

J. B. MacQueen. Some methods for classification and analysis of multivariate observations. In Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, volume 1, pages 281--297. University of California Press, 1967.

[18]

M. E. Newman. Fast algorithm for detecting community structure in networks. Physical Review E, 69:066133, 2004.

[19]

M. E. Newman and M. Girvan. Finding and evaluating community structure in networks. Physical Review E, 69, 2004.

[20]

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

[21]

J. P. Scott. Social Network Analysis: A Handbook. Sage Publications Ltd., 2 edition, 2000.

[22]

J. Shi and J. Malik. Normalized cuts and image segmentation. IEEE. Transactions on Pattern Analysis and Machine Intelligence, 2000.

Digital Library

[23]

S. Wasserman and K. Faust. Social Network Analysis: Methods and Applications. Cambridge University Press, 1994.

[24]

S. White and P. Smyth. A spectral clustering approach to finding communities in graphs. In Proceedings of the 5th SIAM International Conference on Data Mining, pages 76--84, 2005.

[25]

C. Wilson, B. Boe, A. Sala, K. P. Puttaswami, and B. Y. Zhao. User interactions in social networks and their implications. In Proceedings of the 4th ACM European Conference on Computer Systems, pages 205--218. ACM, New York, 2009.

Digital Library

[26]

X. Xu, N. Yuruk, Z. Feng, and T. A. J. Schweiger. SCAN: a structural clustering algorithm for networks. In Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining (KDD '07), pages 824--833. ACM, 2007.

Digital Library

[27]

W. W. Zachary. An information flow model for conflict and fission in small groups. Journal of Anthropological Research, 33:452--473, 1977.

Cited By

Horta VStröele VOliveira JBraga RDavid JCampos F(2022)Detecting topic-based communities in social networksWeb Semantics: Science, Services and Agents on the World Wide Web10.1016/j.websem.2022.10073974:COnline publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1016/j.websem.2022.100739
Horta VStröele VBraga RDavid JCampos F(2018)Analyzing scientific context of researchers and communities by using complex network and semantic technologiesFuture Generation Computer Systems10.1016/j.future.2018.07.01289:C(584-605)Online publication date: 1-Dec-2018
https://dl.acm.org/doi/10.1016/j.future.2018.07.012
Bhat SAbulaish M(2015)HOCTracker: Tracking the Evolution of Hierarchical and Overlapping Communities in Dynamic Social NetworksIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2014.234991827:4(1019-1013)Online publication date: 1-Apr-2015
https://doi.org/10.1109/TKDE.2014.2349918
Show More Cited By

Index Terms

A density-based approach for mining overlapping communities from social network interactions
1. Information systems
  1. Information retrieval
    1. Retrieval tasks and goals
  2. Information systems applications
    1. Data mining
      1. Clustering

Recommendations

OCMiner: A density-based overlapping community detection method for social networks

Community detection is an important task for identifying the structure and function of complex networks. The task is challenging as communities often show overlapping and hierarchical behavior, i.e., a node can belong to multiple communities, and multiple ...
Finding overlapping communities in social networks: toward a rigorous approach
EC '12: Proceedings of the 13th ACM Conference on Electronic Commerce

A community in a social network is usually understood to be a group of nodes more densely connected with each other than with the rest of the network. This is an important concept in most domains where networks arise: social, technological, biological, ...
Density-based semi-supervised clustering

Semi-supervised clustering methods guide the data partitioning and grouping process by exploiting background knowledge, among else in the form of constraints. In this study, we propose a semi-supervised density-based clustering method. Density-based ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

WIMS '12: Proceedings of the 2nd International Conference on Web Intelligence, Mining and Semantics

June 2012

571 pages

ISBN:9781450309158

DOI:10.1145/2254129

Conference Chair:
Dumitru Dan Burdescu
University of Craiova, Romania
,
Program Chairs:
Rajendra Akerkar
Western Norway Research Institute, Norway
,
Costin Bădică
SUniversity of Craiova, Romania

Copyright © 2012 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 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

UCV: University of Craiova
WNRI: Western Norway Research Institute

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 June 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

King Abdulaziz City for Science and Technology

Conference

WIMS '12

Sponsor:

UCV
WNRI

WIMS '12: 2nd International Conference on Web Intelligence, Mining and Semantics

June 13 - 15, 2012

Craiova, Romania

Acceptance Rates

Overall Acceptance Rate 140 of 278 submissions, 50%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
270
Total Downloads

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

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Horta VStröele VOliveira JBraga RDavid JCampos F(2022)Detecting topic-based communities in social networksWeb Semantics: Science, Services and Agents on the World Wide Web10.1016/j.websem.2022.10073974:COnline publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1016/j.websem.2022.100739
Horta VStröele VBraga RDavid JCampos F(2018)Analyzing scientific context of researchers and communities by using complex network and semantic technologiesFuture Generation Computer Systems10.1016/j.future.2018.07.01289:C(584-605)Online publication date: 1-Dec-2018
https://dl.acm.org/doi/10.1016/j.future.2018.07.012
Bhat SAbulaish M(2015)HOCTracker: Tracking the Evolution of Hierarchical and Overlapping Communities in Dynamic Social NetworksIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2014.234991827:4(1019-1013)Online publication date: 1-Apr-2015
https://doi.org/10.1109/TKDE.2014.2349918
Roitman HRaviv AHummel SErera SKonopniki DKuflik TStock OChai JKrüger A(2014)MicrocosmCompanion Proceedings of the 19th International Conference on Intelligent User Interfaces10.1145/2559184.2559195(5-8)Online publication date: 24-Feb-2014
https://dl.acm.org/doi/10.1145/2559184.2559195

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