Multilevel Network Alignment
Multilevel Network Alignment
复制标题
DOI：
10.1145/3308558.3313484
复制
发表时间：
2019-05
期刊：
影响因子：
--
通讯作者：
Si Zhang;Hanghang Tong;Ross Maciejewski;Tina Eliassi-Rad
中科院分区：
文献类型：
--
作者：
Si Zhang;Hanghang Tong;Ross Maciejewski;Tina Eliassi-Rad
网络对齐旨在发现多个网络之间的节点对应关系，在从社会网络分析到敌对活动检测的许多领域中都是一项基本任务。数据挖掘领域的研究现状往往将节点对应关系看作是一个概率的跨网络节点相似度，从而不可避免地引入O(N2)的计算复杂度下界。此外，它们可能会忽略伴随真实网络的丰富模式(例如，集群)。本文提出了一种多层网络对齐算法(MOANA)，该算法由三个关键步骤组成。它首先有效地将输入网络粗化成它们的结构化表示，然后对输入网络的最粗表示进行对齐，然后进行内插以获得多个级别的对齐，包括以最细粒度的节点级别。提出的粗化-对准-插值法具有两个关键优点。首先，它克服了O(N2)的下界，实现了线性复杂度。其次，它有助于揭示输入网络在多个层次(例如，节点、集群、超级集群等)的丰富模式之间的对齐。大量的实验测试表明，该算法在节点级比对和不同粒度的丰富模式(如簇)之间的比对上都是有效的。
Network alignment, which aims to find the node correspondence across multiple networks, is a fundamental task in many areas, ranging from social network analysis to adversarial activity detection. The state-of-the-art in the data mining community often view the node correspondence as a probabilistic cross-network node similarity, and thus inevitably introduce an O(n2) lower bound on the computational complexity. Moreover, they might ignore the rich patterns (e.g., clusters) accompanying the real networks. In this paper, we propose a multilevel network alignment algorithm (Moana) which consists of three key steps. It first efficiently coarsens the input networks into their structured representations, and then aligns the coarsest representations of the input networks, followed by the interpolations to obtain the alignment at multiple levels including the node level at the finest granularity. The proposed coarsen-align-interpolate method bears two key advantages. First, it overcomes the O(n2) lower bound, achieving a linear complexity. Second, it helps reveal the alignment between rich patterns of the input networks at multiple levels (e.g., node, clusters, super-clusters, etc.). Extensive experimental evaluations demonstrate the efficacy of the proposed algorithm on both the node-level alignment and the alignment among rich patterns (e.g., clusters) at different granularities.