A better strategy of discovering link-pattern based communities by classical clustering methods

Chen Yi Lin; Jia Ling Koh; Arbee L.P. Chen

doi:10.1007/978-3-642-13657-3_9

A better strategy of discovering link-pattern based communities by classical clustering methods

Chen Yi Lin^*, Jia Ling Koh, Arbee L.P. Chen

^*Corresponding author for this work

Department of Computer Science and Information Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

6 Citations (Scopus)

Abstract

The definition of a community in social networks varies with applications. To generalize different types of communities, the concept of linkpattern based community was proposed in a previous study to group nodes into communities, where the nodes in a community have similar intra-community and inter-community interaction behaviors. In this paper, by defining centroid of a community, a distance function is provided to measure the similarity between the link pattern of a node and the centroid of a community. The problem of discovering link-pattern based communities is transformed into a data clustering problem on nodes for minimizing a given objective function. By extending the partitioning methods of cluster analysis, two algorithms named G-LPC and KM-LPC are proposed to solve the problem. The experiment results show that KM-LPC outperforms the previous work on the efficiency, the memory utilization, and the clustering result. Besides, G-LPC achieves the best result approaching the optimal solution.

Original language	English
Title of host publication	Advances in Knowledge Discovery and Data Mining - 14th Pacific-Asia Conference, PAKDD 2010, Proceedings
Pages	56-67
Number of pages	12
Edition	PART 1
DOIs	https://doi.org/10.1007/978-3-642-13657-3_9
Publication status	Published - 2010
Event	14th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2010 - Hyderabad, India Duration: 2010 Jun 21 → 2010 Jun 24

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	PART 1
Volume	6118 LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	14th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2010
Country/Territory	India
City	Hyderabad
Period	2010/06/21 → 2010/06/24

Keywords

Clustering algorithms
Link-pattern based community
Social network

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-13657-3_9

Cite this

Lin, C. Y., Koh, J. L., & Chen, A. L. P. (2010). A better strategy of discovering link-pattern based communities by classical clustering methods. In Advances in Knowledge Discovery and Data Mining - 14th Pacific-Asia Conference, PAKDD 2010, Proceedings (PART 1 ed., pp. 56-67). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6118 LNAI, No. PART 1). https://doi.org/10.1007/978-3-642-13657-3_9

A better strategy of discovering link-pattern based communities by classical clustering methods. / Lin, Chen Yi; Koh, Jia Ling; Chen, Arbee L.P.
Advances in Knowledge Discovery and Data Mining - 14th Pacific-Asia Conference, PAKDD 2010, Proceedings. PART 1. ed. 2010. p. 56-67 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6118 LNAI, No. PART 1).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Lin, CY, Koh, JL & Chen, ALP 2010, A better strategy of discovering link-pattern based communities by classical clustering methods. in Advances in Knowledge Discovery and Data Mining - 14th Pacific-Asia Conference, PAKDD 2010, Proceedings. PART 1 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 1, vol. 6118 LNAI, pp. 56-67, 14th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2010, Hyderabad, India, 2010/06/21. https://doi.org/10.1007/978-3-642-13657-3_9

Lin CY, Koh JL, Chen ALP. A better strategy of discovering link-pattern based communities by classical clustering methods. In Advances in Knowledge Discovery and Data Mining - 14th Pacific-Asia Conference, PAKDD 2010, Proceedings. PART 1 ed. 2010. p. 56-67. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1). doi: 10.1007/978-3-642-13657-3_9

Lin, Chen Yi ; Koh, Jia Ling ; Chen, Arbee L.P. / A better strategy of discovering link-pattern based communities by classical clustering methods. Advances in Knowledge Discovery and Data Mining - 14th Pacific-Asia Conference, PAKDD 2010, Proceedings. PART 1. ed. 2010. pp. 56-67 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1).

@inproceedings{f2131a9823e9461eb2e89751a53dea50,

title = "A better strategy of discovering link-pattern based communities by classical clustering methods",

abstract = "The definition of a community in social networks varies with applications. To generalize different types of communities, the concept of linkpattern based community was proposed in a previous study to group nodes into communities, where the nodes in a community have similar intra-community and inter-community interaction behaviors. In this paper, by defining centroid of a community, a distance function is provided to measure the similarity between the link pattern of a node and the centroid of a community. The problem of discovering link-pattern based communities is transformed into a data clustering problem on nodes for minimizing a given objective function. By extending the partitioning methods of cluster analysis, two algorithms named G-LPC and KM-LPC are proposed to solve the problem. The experiment results show that KM-LPC outperforms the previous work on the efficiency, the memory utilization, and the clustering result. Besides, G-LPC achieves the best result approaching the optimal solution.",

keywords = "Clustering algorithms, Link-pattern based community, Social network",

author = "Lin, {Chen Yi} and Koh, {Jia Ling} and Chen, {Arbee L.P.}",

year = "2010",

doi = "10.1007/978-3-642-13657-3_9",

language = "English",

isbn = "3642136567",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

number = "PART 1",

pages = "56--67",

booktitle = "Advances in Knowledge Discovery and Data Mining - 14th Pacific-Asia Conference, PAKDD 2010, Proceedings",

edition = "PART 1",

note = "14th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2010 ; Conference date: 21-06-2010 Through 24-06-2010",

}

TY - GEN

T1 - A better strategy of discovering link-pattern based communities by classical clustering methods

AU - Lin, Chen Yi

AU - Koh, Jia Ling

AU - Chen, Arbee L.P.

PY - 2010

Y1 - 2010

N2 - The definition of a community in social networks varies with applications. To generalize different types of communities, the concept of linkpattern based community was proposed in a previous study to group nodes into communities, where the nodes in a community have similar intra-community and inter-community interaction behaviors. In this paper, by defining centroid of a community, a distance function is provided to measure the similarity between the link pattern of a node and the centroid of a community. The problem of discovering link-pattern based communities is transformed into a data clustering problem on nodes for minimizing a given objective function. By extending the partitioning methods of cluster analysis, two algorithms named G-LPC and KM-LPC are proposed to solve the problem. The experiment results show that KM-LPC outperforms the previous work on the efficiency, the memory utilization, and the clustering result. Besides, G-LPC achieves the best result approaching the optimal solution.

AB - The definition of a community in social networks varies with applications. To generalize different types of communities, the concept of linkpattern based community was proposed in a previous study to group nodes into communities, where the nodes in a community have similar intra-community and inter-community interaction behaviors. In this paper, by defining centroid of a community, a distance function is provided to measure the similarity between the link pattern of a node and the centroid of a community. The problem of discovering link-pattern based communities is transformed into a data clustering problem on nodes for minimizing a given objective function. By extending the partitioning methods of cluster analysis, two algorithms named G-LPC and KM-LPC are proposed to solve the problem. The experiment results show that KM-LPC outperforms the previous work on the efficiency, the memory utilization, and the clustering result. Besides, G-LPC achieves the best result approaching the optimal solution.

KW - Clustering algorithms

KW - Link-pattern based community

KW - Social network

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

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

U2 - 10.1007/978-3-642-13657-3_9

DO - 10.1007/978-3-642-13657-3_9

M3 - Conference contribution

AN - SCOPUS:79956292361

SN - 3642136567

SN - 9783642136566

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 56

EP - 67

BT - Advances in Knowledge Discovery and Data Mining - 14th Pacific-Asia Conference, PAKDD 2010, Proceedings

T2 - 14th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2010

Y2 - 21 June 2010 through 24 June 2010

ER -

A better strategy of discovering link-pattern based communities by classical clustering methods

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this