Date of Award

3-18-2009

Document Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Department

Applied Science

First Advisor

Xiaowei Xu

Abstract

The tightly connected groups of entities, so-called modules or clusters, are usually good indicators of structural or functional units of the underlying network. While those units are communities of people in a social network, they refer to web pages of similar topic on WWW, group of molecules that work together to achieve certain biological function in a biological network and etc. Modular structure is one of the most important and ubiquitous features observed in most complex networks and we mainly target the problem of network clustering which has, among other network analysis tasks, particular role of detecting modules in given networks. In this dissertation, we present a new network clustering algorithm, namely SCAN (Structural Clustering Algorithm for Networks), which runs linearly with the size of given network. Despite the common methodology of current methods where maximization or minimization of edges within/across clusters is essential, it defines clusters based on structural similarity of vertices. SCAN not only finds groups of peers in networks, it also identifies vertices that play special roles such as hubs that bridge clusters and outsiders that are marginally connected to clusters. In fact, identification and isolation of such nodes is essential for many applications such as viral marketing, epidemiology, WWW, etc. An empirical evaluation of the SCAN algorithm using both synthetic and real datasets demonstrates superior performance over other methods such as modularity-based graph partitioning algorithm both in terms of clustering accuracy and running time. In this study, in addition to SCAN's adaptation to directed and weighted networks, we also provide hierarchical versions of SCAN.

Download

Share

COinS