Biology Reference
In-Depth Information
Chapter 11
A Novel Similarity-based Modularity Function for Graph
Partitioning
Zhidan Feng
Acxiom Corporation, USA, dafeng@acxiom.com
Xiaowei Xu
Department of Information Science, UALR, USA, xwxu@ualr.edu
Nurcan Yuruk
Department of Information Science, UALR, USA, nxyuruk@ualr.edu
Thomas Schweiger
Acxiom Corporation, USA, Tom.Schweiger@acxiom.com
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 are less able to deal with very confused structures. In this paper we
propose a novel similarity-based definition of the quality of a partitioning of a
graph. Through theoretical analysis and experimental results we demonstrate
that the proposed definition largely overcomes the “hub” problem and outper-
forms existing approaches on complicated graphs. In addition, we show that this
definition can be used with fast agglomerative algorithms to find communities in
very large networks.
11.1. Introduction
Many problems can be modeled as networks or graphs, and identifying cluster in
the network or partitioning the graph is a fundamental problem for computer net-
works analysis, VLSI design, biological network analysis, social networks analy-
sis [18], business networks analysis, and community detection [6]. In the litera-
ture, graph partitioning has many names, and is sometimes called network anal-
ysis, network clustering, detecting communities in networks, etc.
This area of
223
Search WWH ::
Custom Search