Graph partitioning, or network clustering, is an essential research problem in many areas. Current approaches, however, have
difficulty splitting two clusters that are densely connected by one or more “hub” vertices. Further, traditional methods areless able to deal with very confused structures. In this paper we propose a novel similarity-based definition of the qualityof a partitioning of a graph. Through theoretical analysis and experimental results we demonstrate that the proposed definitionlargely overcomes the “hub” problem and outperforms existing approaches on complicated graphs. In addition, we show that thisdefinition can be used with fast agglomerative algorithms to find communities in very large networks.
%0 Journal Article
%1 Feng07similarityModularity
%A Feng, Zhidan
%A Xu, Xiaowei
%A Yuruk, Nurcan
%A Schweiger, Thomas
%D 2007
%J Data Warehousing and Knowledge Discovery
%K community detection measure modularity similarity
%P 385--396
%T A Novel Similarity-Based Modularity Function for Graph Partitioning
%U http://dx.doi.org/10.1007/978-3-540-74553-2_36
%X Graph partitioning, or network clustering, is an essential research problem in many areas. Current approaches, however, have
difficulty splitting two clusters that are densely connected by one or more “hub” vertices. Further, traditional methods areless able to deal with very confused structures. In this paper we propose a novel similarity-based definition of the qualityof a partitioning of a graph. Through theoretical analysis and experimental results we demonstrate that the proposed definitionlargely overcomes the “hub” problem and outperforms existing approaches on complicated graphs. In addition, we show that thisdefinition can be used with fast agglomerative algorithms to find communities in very large networks.
@article{Feng07similarityModularity,
abstract = {Graph partitioning, or network clustering, is an essential research problem in many areas. Current approaches, however, have
difficulty splitting two clusters that are densely connected by one or more “hub” vertices. Further, traditional methods areless able to deal with very confused structures. In this paper we propose a novel similarity-based definition of the qualityof a partitioning of a graph. Through theoretical analysis and experimental results we demonstrate that the proposed definitionlargely overcomes the “hub” problem and outperforms existing approaches on complicated graphs. In addition, we show that thisdefinition can be used with fast agglomerative algorithms to find communities in very large networks.},
added-at = {2016-12-02T13:06:09.000+0100},
author = {Feng, Zhidan and Xu, Xiaowei and Yuruk, Nurcan and Schweiger, Thomas},
biburl = {https://www.bibsonomy.org/bibtex/27ec2869aa9b34da0643a49173eb59f7b/ans},
description = {SpringerLink - Book Chapter},
interhash = {af9f9ec41234f5d01c7bd8012a501590},
intrahash = {7ec2869aa9b34da0643a49173eb59f7b},
journal = {Data Warehousing and Knowledge Discovery},
keywords = {community detection measure modularity similarity},
pages = {385--396},
timestamp = {2016-12-02T13:06:09.000+0100},
title = {A Novel Similarity-Based Modularity Function for Graph Partitioning},
url = {http://dx.doi.org/10.1007/978-3-540-74553-2_36},
year = 2007
}