中文摘要：

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

英文摘要：

The graph could be quickly zoom-out for a social network. A smaller equivalent graph was got to preserve its propa- gation 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. This paper proposed a novel graph coarsening problem to find an approximate graph to preserve key characteristics for propagation processes on the graph. Then it proposed a fast and effective near-linear time algorithm to tackle this problem. Experiments were conducted on multiple real datasets. The results demonstrate the quality and scalability of this method. Experimental results show the graph is reduced by 90% according ＇to this method.