Social network pruning for building optimal social network: A user perspective

摘要

Social networks with millions of nodes and edges are difficult to visualize and understand. Therefore, approaches to simplify social networks are needed. This paper addresses the problem of pruning social network while not only retaining but also improving its information propagation properties. The paper presents an approach which examines the nodal attribute of a node and develops a criterion to retain a subset of nodes to form a pruned graph of the original social network. To authenticate feasibility of the proposed approach to information propagation process, it is evaluated on small world properties such as average clustering coefficient, diameter, path length, connected components and modularity. The pruned graph, when compared to original social network, shows improvement in small world properties which are essential for information propagation. Results also give a significantly more refined picture of social network, than has been previously highlighted. The efficacy of the pruned graph is demonstrated in the information diffusion process under Independent Cascade (IC) and Linear Threshold (LT) models on various seeding strategies. In all size ranges and across various seeding strategies, the proposed approach performs consistently well in IC model and outperforms other approaches in LT model. Although, the paper discusses the problem with the context of information propagation for viral marketing, the pruned graph generated from the proposed approach is also suitable for any application, where information propagation has to take place reasonably fast and effectively.