Weighted-spectral clustering algorithm for detecting community structures in complex networks

Tzy Shiah Wang, Hui Tang Lin, Ping Wang

Research output: Contribution to journalArticle

6 Citations (Scopus)

Abstract

The community structure is a common non-trivial topological feature of many complex real-world networks. Existing methods for identifying the community structure are generally based on statistical-type properties, such as the degree of centrality, the shortest path betweenness centrality, the modularity, and so forth. However, the form of the community structure may vary widely, even if the number of vertices and edges are fixed. Consequently, it is difficult to be certain of the exact number of clusters within the network. Clustering schemes which require the number of clusters to be specified in advance often misjudge the community structure and yield a poor clustering performance as a result. Accordingly, the present study proposes a clustering algorithm, designated as the Weighted-Spectral Clustering Algorithm, capable of detecting the community structure of a network with no prior knowledge of the cluster number. The proposed method is tested on both computer-generated networks and several real-world networks for which the community structures are already known. The results confirm the ability of the proposed algorithm to partition the network into an appropriate number of clusters in every case.

Original languageEnglish
Pages (from-to)463-483
Number of pages21
JournalArtificial Intelligence Review
Volume47
Issue number4
DOIs
Publication statusPublished - 2017 Apr 1

Fingerprint

Complex networks
Clustering algorithms
community
Spectrality
Complex Networks
ability
knowledge
performance

All Science Journal Classification (ASJC) codes

  • Language and Linguistics
  • Linguistics and Language
  • Artificial Intelligence

Cite this

@article{76bbb2286b454f5795b71fb480e47eeb,
title = "Weighted-spectral clustering algorithm for detecting community structures in complex networks",
abstract = "The community structure is a common non-trivial topological feature of many complex real-world networks. Existing methods for identifying the community structure are generally based on statistical-type properties, such as the degree of centrality, the shortest path betweenness centrality, the modularity, and so forth. However, the form of the community structure may vary widely, even if the number of vertices and edges are fixed. Consequently, it is difficult to be certain of the exact number of clusters within the network. Clustering schemes which require the number of clusters to be specified in advance often misjudge the community structure and yield a poor clustering performance as a result. Accordingly, the present study proposes a clustering algorithm, designated as the Weighted-Spectral Clustering Algorithm, capable of detecting the community structure of a network with no prior knowledge of the cluster number. The proposed method is tested on both computer-generated networks and several real-world networks for which the community structures are already known. The results confirm the ability of the proposed algorithm to partition the network into an appropriate number of clusters in every case.",
author = "Wang, {Tzy Shiah} and Lin, {Hui Tang} and Ping Wang",
year = "2017",
month = "4",
day = "1",
doi = "10.1007/s10462-016-9488-4",
language = "English",
volume = "47",
pages = "463--483",
journal = "Artificial Intelligence Review",
issn = "0269-2821",
publisher = "Springer Netherlands",
number = "4",

}

Weighted-spectral clustering algorithm for detecting community structures in complex networks. / Wang, Tzy Shiah; Lin, Hui Tang; Wang, Ping.

In: Artificial Intelligence Review, Vol. 47, No. 4, 01.04.2017, p. 463-483.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Weighted-spectral clustering algorithm for detecting community structures in complex networks

AU - Wang, Tzy Shiah

AU - Lin, Hui Tang

AU - Wang, Ping

PY - 2017/4/1

Y1 - 2017/4/1

N2 - The community structure is a common non-trivial topological feature of many complex real-world networks. Existing methods for identifying the community structure are generally based on statistical-type properties, such as the degree of centrality, the shortest path betweenness centrality, the modularity, and so forth. However, the form of the community structure may vary widely, even if the number of vertices and edges are fixed. Consequently, it is difficult to be certain of the exact number of clusters within the network. Clustering schemes which require the number of clusters to be specified in advance often misjudge the community structure and yield a poor clustering performance as a result. Accordingly, the present study proposes a clustering algorithm, designated as the Weighted-Spectral Clustering Algorithm, capable of detecting the community structure of a network with no prior knowledge of the cluster number. The proposed method is tested on both computer-generated networks and several real-world networks for which the community structures are already known. The results confirm the ability of the proposed algorithm to partition the network into an appropriate number of clusters in every case.

AB - The community structure is a common non-trivial topological feature of many complex real-world networks. Existing methods for identifying the community structure are generally based on statistical-type properties, such as the degree of centrality, the shortest path betweenness centrality, the modularity, and so forth. However, the form of the community structure may vary widely, even if the number of vertices and edges are fixed. Consequently, it is difficult to be certain of the exact number of clusters within the network. Clustering schemes which require the number of clusters to be specified in advance often misjudge the community structure and yield a poor clustering performance as a result. Accordingly, the present study proposes a clustering algorithm, designated as the Weighted-Spectral Clustering Algorithm, capable of detecting the community structure of a network with no prior knowledge of the cluster number. The proposed method is tested on both computer-generated networks and several real-world networks for which the community structures are already known. The results confirm the ability of the proposed algorithm to partition the network into an appropriate number of clusters in every case.

UR - http://www.scopus.com/inward/record.url?scp=84975125255&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84975125255&partnerID=8YFLogxK

U2 - 10.1007/s10462-016-9488-4

DO - 10.1007/s10462-016-9488-4

M3 - Article

AN - SCOPUS:84975125255

VL - 47

SP - 463

EP - 483

JO - Artificial Intelligence Review

JF - Artificial Intelligence Review

SN - 0269-2821

IS - 4

ER -