Community-Based Network Alignment for Large Attributed Network
Community-Based Network Alignment for Large Attributed Network
复制标题
DOI：
10.1145/3132847.3132904
复制
发表时间：
2017-11
期刊：
影响因子：
--
通讯作者：
Zheng Chen;Xinli Yu;Bo Song;Jianliang Gao;Xiaohua Hu;Wei-Shih Yang
中科院分区：
文献类型：
--
作者：
Zheng Chen;Xinli Yu;Bo Song;Jianliang Gao;Xiaohua Hu;Wei-Shih Yang
网络对齐已成为网络数据分析中的一个活跃话题。尽管进行了广泛的研究，但我们意识到，在以往的研究中，对大型属性网络对齐的拓扑和属性信息的有效利用尚未得到充分的解决。本文基于随机块模型（SBM）和dirichlet -多项式，针对具有节点属性的大型网络，提出了“分而治之”模型，该模型在一个框架内共同考虑网络排列、社区发现和社区排列，以减少计算时间和内存使用，同时获得更好的或有竞争力的性能。证明了该模型的算法在小密度网络上具有次二次时间复杂度和线性空间复杂度，这对大多数现实网络都是成立的。实验表明，在大型网络上，CAlign在准确性、时间和内存方面优于最近两种最先进的模型，而且CAlign能够在现代台式计算机上处理数百万个节点。
Network alignment is becoming an active topic in network data analysis. Despite extensive research, we realize that efficient use of topological and attribute information for large attributed network alignment has not been sufficiently addressed in previous studies. In this paper, based on Stochastic Block Model (SBM) and Dirichlet-multinomial, we propose "divide-and-conquer" models CAlign that jointly consider network alignment, community discovery and community alignment in one framework for large networks with node attributes, in an effort to reduce both the computation time and memory usage while achieving better or competitive performance. It is provable that the algorithms derived from our model have sub-quadratic time complexity and linear space complexity on a network with small densification power, which is true for most real-world networks. Experiments show CAlign is superior to two recent state-of-art models in terms of accuracy, time and memory on large networks, and CAlign is capable of handling millions of nodes on a modern desktop machine.