A Dimensionality Reduction Framework for Detection of Multiscale Structure in Heterogeneous Networks
A Dimensionality Reduction Framework for Detection of Multiscale Structure in Heterogeneous Networks
复制标题
DOI：
10.1007/s11390-012-1227-y
复制
发表时间：
2012-03
影响因子：
0.7
通讯作者：
Huawei Shen;Xueqi Cheng;Yuanzhuo Wang;Yixin Chen
中科院分区：
文献类型：
--
作者：
Huawei Shen;Xueqi Cheng;Yuanzhuo Wang;Yixin Chen
图聚类在探索关系数据中出现的规律方面得到了广泛的应用。近年来，网络理论的快速发展将图聚类与社区结构检测联系起来，社区结构是网络的一个共同而重要的拓扑特征。现有的方法大多是在单一的拓扑尺度上研究群落结构。然而，实证研究表明，现实世界网络的社区结构往往呈现出多种拓扑描述，对应于不同分辨率的聚类。此外，节点度的非均匀分布严重影响多尺度群落结构的检测。异构网络中多尺度社团结构的检测是一个非常具有挑战性的问题。本文从降维的角度提出了一种新的、统一的群落结构检测框架。基于该框架，我们首先证明了用于网络划分的拉普拉斯矩阵和用于社区检测的模块化矩阵是两种用于降维的协方差矩阵。然后，我们提出了一种新的方法来检测我们框架内多个拓扑尺度上的群落。我们进一步表明，现有算法无法处理异构节点度。我们开发了一种新的方法，通过在我们的框架中引入协方差矩阵的重新缩放变换来处理网络的异质性。
Graph clustering has been widely applied in exploring regularities emerging in relational data. Recently, the rapid development of network theory correlates graph clustering with the detection of community structure, a common and important topological characteristic of networks. Most existing methods investigate the community structure at a single topological scale. However, as shown by empirical studies, the community structure of real world networks often exhibits multiple topological descriptions, corresponding to the clustering at different resolutions. Furthermore, the detection of multiscale community structure is heavily affected by the heterogeneous distribution of node degree. It is very challenging to detect multiscale community structure in heterogeneous networks. In this paper, we propose a novel, unified framework for detecting community structure from the perspective of dimensionality reduction. Based on the framework, we first prove that the well-known Laplacian matrix for network partition and the widely-used modularity matrix for community detection are two kinds of covariance matrices used in dimensionality reduction. We then propose a novel method to detect communities at multiple topological scales within our framework. We further show that existing algorithms fail to deal with heterogeneous node degrees. We develop a novel method to handle heterogeneity of networks by introducing a rescaling transformation into the covariance matrices in our framework.