Is objective function the silver bullet? A case study of community detection algorithms on social networks

Yang Yang*, Yizhou Sun, Saurav Pandit, Nitesh V. Chawla, Jiawei Han

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

Abstract

Community detection or cluster detection in networks is a well-studied, albeit hard, problem. Given the scale and complexity of modern day social networks, detecting "reasonable" communities is an even harder problem. Since the first use of k-means algorithm in 1960s, many community detection algorithms have been invented - most of which are developed with specific goals in mind and the idea of detecting "meaningful" communities varies widely from one algorithm to another. With the increasing number of community detection algorithms, there has been an advent of a number of evaluation measures and objective functions such as modularity and internal density. In this paper we divide methods of measurements in to two categories, according to whether they rely on ground-truth or not. Our work is aiming to answer whether these general used objective functions are well consistent with the real performance of community detection algorithms across a number of homogeneous and heterogeneous networks. Seven representative algorithms are compared under various performance metrics, and on various real world social networks.

Original languageEnglish (US)
Title of host publicationProceedings - 2011 International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2011
Pages394-397
Number of pages4
DOIs
StatePublished - Sep 19 2011
Event2011 International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2011 - Kaohsiung, Taiwan, Province of China
Duration: Jul 25 2011Jul 27 2011

Publication series

NameProceedings - 2011 International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2011

Other

Other2011 International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2011
CountryTaiwan, Province of China
CityKaohsiung
Period7/25/117/27/11

Keywords

  • Benchmark network
  • Community detection
  • Measurements
  • Objective functions
  • Social network

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Is objective function the silver bullet? A case study of community detection algorithms on social networks'. Together they form a unique fingerprint.

  • Cite this

    Yang, Y., Sun, Y., Pandit, S., Chawla, N. V., & Han, J. (2011). Is objective function the silver bullet? A case study of community detection algorithms on social networks. In Proceedings - 2011 International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2011 (pp. 394-397). [5992630] (Proceedings - 2011 International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2011). https://doi.org/10.1109/ASONAM.2011.111