基于影响力的大规模社会网络快速粗化方法

给定社会网络，如何快速地粗化社会网络图，是否能够在社会网络图中找到更小的等价表示来保持社会网络的传播特征，是否能够基于节点的影响力属性合并社会网络中的部分节点。这些重要的问题能够应用到影响力分析，流行病学和病毒营销的应用。首先本文提出了一种新颖的图粗化问题，目的为不改变信息扩散过程中的关键特征来发现图代表节点和边。随后提出了一种快速的和有效的算法来解决图粗化问题。本文做了大量的实验，实验构造在多个真实的数据，验证了算法的性能和可扩展性，且实验在没有损失图信息的情况下，将图规模降低了90%。

A Fast Graph Coarsening Problem based on Influence for Large Networks

Abstract: The graph can be quickly zoom-out for a social network. A smaller equivalent graph was got to preserve its propagation characteristics. Nodes pairs were merged based on influence properties. Graph coarsening was an important problems with applications to influence analysis, epidemiology and viral marketing applications. In this paper, a novel graph coarsening problem was proposed to find an approximate graph to preserve key characteristics for propagation processes on the graph. A fast and effective near-linear time algorithm was proposed to tackle this problem. Experiments were conducted on multiple real datasets. The quality and scalability of our method were demonstrated. Experimental results showed the graph was reduced by 90% according to our method.