Continuous Influence-Based Community Partition for Social Networks

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 Linear Threshold (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 within each community. As the influence propagation function of community partition problem is supermodular under LT model, we use the method of Lovisz 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 the 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. The results demonstrate that continuous community partition method can improve influence spread and accuracy of the community partition effectively.

Automated summary

Community partition is crucial in social networks, particularly in the face of network growth and increased data and applications. This study focuses on the community partition problem under the Linear Threshold (LT) model, aiming to maximize influence propagation within each community. The proposed continuous greedy algorithm, which exploits the properties of the relaxed function, is able to effectively improve influence spread and accuracy of the community partition. Theoretical analysis demonstrates a 1 - 1/e approximation ratio for the algorithm, while extensive experiments on real-world online social networks datasets validate its performance.