Issue Eur. Phys. J. B Volume 57, Number 1, May I 2007 Page(s) 67 - 74 DOI 10.1140/epjb/e2007-00146-y Published online 25 May 2007

Eur. Phys. J. B 57, 67-74 (2007)
DOI: 10.1140/epjb/e2007-00146-y

Graph kernels, hierarchical clustering, and network community structure: experiments and comparative analysis

S. Zhang^{1, 2}, X.-M. Ning^{1, 2} and X.-S. Zhang<sup>1

1</sup>  Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100080, P.R. China
²  Graduate University of Chinese Academy of Sciences, Beijing 100049, P.R. China

zsh@amss.ac.cn

(Received 12 July 2006 / Received in final form 20 April 2007 / Published online 25 May 2007)

Abstract
There has been a quickly growing interest in properties of complex networks, such as the small world property, power-law degree distribution, network transitivity, and community structure, which seem to be common to many real world networks. In this study, we consider the community property which is also found in many real networks. Based on the diffusion kernels of networks, a hierarchical clustering approach is proposed to uncover the community structure of different extent of complex networks. We test the method on some networks with known community structures and find that it can detect significant community structure in these networks. Comparison with related methods shows the effectiveness of the method.

PACS
89.75.Hc - Networks and genealogical trees.
89.65.-s - Social and economic systems.
05.10.-a - Computational methods in statistical physics and nonlinear dynamics.

© EDP Sciences, Società Italiana di Fisica, Springer-Verlag 2007

What is OpenURL?