Title :
Linear Computation for Independent Social Influence
Author :
Qi Liu ; Biao Xiang ; Lei Zhang ; Enhong Chen ; Chang Tan ; Ji Chen
Author_Institution :
Sch. of Comput. Sci. & Technol., Univ. of Sci. & Technol. of China, Hefei, China
Abstract :
Recent years have witnessed the increased interests in exploiting influence in social networks for many applications. To the best of our knowledge, from the computational aspect of social influence analysis, most of existing work focus on either describing the influence propagation process or identifying the set of most influential seed nodes. However, these work usually do not distinguish the "independent influence" of each single seed node after removing other seeds. Since it is important to quickly figure out the real contribution of each seed, in this paper we propose to measure the seed\´s independent influence by a linear social influence model. Specifically, we first describe the linear social influence model, and then define the independent influence under this model for eliminating the "mutual enrichment" between seed nodes. Meanwhile, we find that the influence of a set of nodes is actually the sum of their independent influence, and we also give upper bounds for independent influence. Moreover, these findings are evaluated by two applications, i.e., ranking the seeds by their independent influence and identifying the Top-K influential ones. Finally, the experimental results on several real-world datasets validate the effectiveness and efficiency of the proposed independent social influence measures.
Keywords :
social networking (online); independent social influence analysis; independent social influence measures; influence propagation process; influential seed nodes; linear computation; linear social influence model; social networks; top-k influential seed identification; Computational modeling; Equations; Integrated circuit modeling; Mathematical model; Upper bound; Vectors; Independent; Linear Computation; Ranking; Social influence; Upper Bound;
Conference_Titel :
Data Mining (ICDM), 2013 IEEE 13th International Conference on
Conference_Location :
Dallas, TX
DOI :
10.1109/ICDM.2013.48