Sorry, you need to enable JavaScript to visit this website.

facebooktwittermailshare

HACD: Hierarchical Agglomerative Community Detection in Social Networks

Abstract: 

Communities (also referred to as clusters) are essential building blocks of all networks. Hierarchical clustering methods are common graph-based approaches for graph clustering. Traditional hierarchical clustering algorithms proceed in a bottom-up or top-down fashion to encode global information in the graph and cluster according to the global modularity of the graph. In this paper, we propose an efficient Hierarchical Agglomerative Community Detection (HACD) algorithm, that combines the local information in a graph with membership propagation to solve the problem, achieving 10-25% quality improvement overall baselines. The first contribution of this paper is to present the fundamental limitations of the general modularity optimization-based approach. We show that based only on modularity information, the method does not provide high-quality clusters. Furthermore, even with modularity optimization, we experimentally show that the final level partitioning of such methods cannot successfully cluster data that contain highly mixed structures at different levels and densities. Based on these findings, the second contribution of this paper is a novel method to propagate knowledge throughout the graph, to split or merge the communities in order to evaluate the consistency of individual clusters. Our approach is bottom-up graph-based clustering, is scale-free, and can determine clusters at all scales. We extensively evaluate HACD’s performance in comparison to state-of-the-art approaches across six real-world and seven synthetic benchmark datasets and demonstrate that HACD, through combining graph’s local information and membership propagation, outperforms the baselines in terms of finding well-integrated communities.

up
1 user has voted: Ekta Gujral

Paper Details

Authors:
Submitted On:
12 October 2019 - 5:58pm
Short Link:
Type:
Presentation Slides
Event:
Presenter's Name:
Evangelos E. Papalexakis
Document Year:
2019
Cite

Document Files

HACD: Hierarchical Agglomerative Community Detection in Social Networks

(13)

Subscribe

[1] , "HACD: Hierarchical Agglomerative Community Detection in Social Networks", IEEE SigPort, 2019. [Online]. Available: http://sigport.org/4862. Accessed: Nov. 15, 2019.
@article{4862-19,
url = {http://sigport.org/4862},
author = { },
publisher = {IEEE SigPort},
title = {HACD: Hierarchical Agglomerative Community Detection in Social Networks},
year = {2019} }
TY - EJOUR
T1 - HACD: Hierarchical Agglomerative Community Detection in Social Networks
AU -
PY - 2019
PB - IEEE SigPort
UR - http://sigport.org/4862
ER -
. (2019). HACD: Hierarchical Agglomerative Community Detection in Social Networks. IEEE SigPort. http://sigport.org/4862
, 2019. HACD: Hierarchical Agglomerative Community Detection in Social Networks. Available at: http://sigport.org/4862.
. (2019). "HACD: Hierarchical Agglomerative Community Detection in Social Networks." Web.
1. . HACD: Hierarchical Agglomerative Community Detection in Social Networks [Internet]. IEEE SigPort; 2019. Available from : http://sigport.org/4862