Efficiently summarizing attributed diffusion networks
Efficiently summarizing attributed diffusion networks
复制标题
DOI：
10.1007/s10618-018-0572-z
复制
发表时间：
2018-05
影响因子：
4.8
通讯作者：
Sorour E. Amiri;Liangzhe Chen;B. Prakash
中科院分区：
文献类型：
--
作者：
Sorour E. Amiri;Liangzhe Chen;B. Prakash
给定一个大型的属性社交网络，我们能否在保持属性属性的同时找到一个紧凑的、扩散等效的表示？具有友谊、电子邮件通信和人员联系网络等用户属性的扩散网络在现实世界中越来越普遍。然而，由于它们的尺寸很大，分析它们具有挑战性。在本文中，我们首先正式提出一个新问题，即总结归因扩散图以保留其属性和基于影响的属性。接下来，我们提出 ANeTS，一种有效的次二次并行化算法来解决这个问题：它找到最佳的候选节点集并将它们合并以构建一个较小的“超级节点”网络，保留所需的属性。对不同现实世界数据集的大量实验表明，ANeTS 的性能优于所有最先进的基线（其中一些甚至无法在 14 天内完成）。最后，我们展示了 ANeTS 如何在多种应用中提供帮助，例如主题感知病毒式营销和来自不同领域的各种图表的意义构建。
Given a large attributed social network, can we find a compact, diffusion-equivalent representation while keeping the attribute properties? Diffusion networks with user attributes such as friendship, email communication, and people contact networks are increasingly common-place in the real-world. However, analyzing them is challenging due to their large size. In this paper, we first formally formulate a novel problem of summarizing an attributed diffusion graph to preserve its attributes and influence-based properties. Next, we propose ANeTS, an effective sub-quadratic parallelizable algorithm to solve this problem: it finds the best set of candidate nodes and merges them to construct a smaller network of ‘super-nodes’ preserving the desired properties. Extensive experiments on diverse real-world datasets show that ANeTS outperforms all state-of-the-art baselines (some of which do not even finish in14 days). Finally, we show how ANeTS helps in multiple applications such as Topic-Aware viral marketing and sense-making of diverse graphs from different domains.