论文标题
社交网络的基于影响力的社区分区
Continuous Influence-based Community Partition for Social Networks
论文作者
论文摘要
由于网络量表，数据和应用程序的迅速增加，社区分区在社交网络中至关重要。我们考虑了社交网络中LT模型下的社区分区问题，这是一个组合优化问题，将社交网络划分为脱节$ m $社区。我们的目标是通过在每个社区中最大化影响力的总和来最大化影响的传播。由于在LT模型下，社区分区问题的影响力传播功能是超模型，因此我们使用LOV {$ \ actute {a} $} SZ扩展的方法来放宽目标影响功能并传递我们的目标，以最大程度地利用矩阵多功能物质来最大程度地利用宽松的功能。接下来，我们使用宽松函数的属性来解决我们的问题，提出一种连续的贪婪算法，需要在具体实施中离散化。然后，随机圆形技术用于将分数溶液转换为整数解决方案。我们为提出的算法提供了$ 1-1/e $ $近似值的理论分析。进行了广泛的实验，以评估现实世界中在线社交网络数据集上提出的连续贪婪算法的性能，结果表明，连续的社区分区方法可以有效地改善社区分区的影响力传播和准确性。
Community partition is of great importance in social networks because of the rapid increasing network scale, data and applications. We consider the community partition problem under LT model in social networks, which is a combinatorial optimization problem that divides the social network to disjoint $m$ communities. Our goal is to maximize the sum of influence propagation through maximizing it within each community. As the influence propagation function of community partition problem is supermodular under LT model, we use the method of Lov{$\acute{a}$}sz Extension to relax the target influence function and transfer our goal to maximize the relaxed function over a matroid polytope. Next, we propose a continuous greedy algorithm using the properties of the relaxed function to solve our problem, which needs to be discretized in concrete implementation. Then, random rounding technique is used to convert the fractional solution to integer solution. We present a theoretical analysis with $1-1/e$ approximation ratio for the proposed algorithms. Extensive experiments are conducted to evaluate the performance of the proposed continuous greedy algorithms on real-world online social networks datasets and the results demonstrate that continuous community partition method can improve influence spread and accuracy of the community partition effectively.
