TY - GEN

T1 - Maximizing information spread through influence structures in social networks

AU - Pandit, Saurav

AU - Yang, Yang

AU - Chawla, Nitesh V.

PY - 2012

Y1 - 2012

N2 - Finding the most influential nodes in a network is a much discussed research topic of recent time in the area of network science, especially in social network analysis. The topic of this paper is a related, but harder problem. Given a social network where neighbors can influence each other, the problem is to identify k nodes such that if a piece of information is placed on each of those k nodes, the overall spread of that information (via word-of-mouth or other methods of influence flow) is maximized. The amount of information spread can be measured using existing information propagation models. Recent studies, which focus on how quickly k high-influential nodes can be found, tend to ignore the overall effect of the information spread. On the other hand some legacy methods, which look at all possible propagation paths to compute a globally optimal target set, present severe scalability challenges in large-scale networks. We present a simple, yet scalable (polynomial time) algorithm that outperforms the existing state-of the-art, and its success does not depend significantly on any kind of tuning parameter. To be more precise, when compared to the existing algorithms, the output set of k nodes produced by our algorithm facilitates higher information spread - in almost all the instances, consistently across the commonly used information propagation models. The original algorithm in this paper, although scalable, can have higher running time than some standard approaches, e.g. simply picking the top k nodes with highest degree or highest Page Rank value. To that end, we provide an optional speedup mechanism that considerably reduces the time complexity while not significantly affecting the quality of results vis-a-vis the full version of our algorithm.

AB - Finding the most influential nodes in a network is a much discussed research topic of recent time in the area of network science, especially in social network analysis. The topic of this paper is a related, but harder problem. Given a social network where neighbors can influence each other, the problem is to identify k nodes such that if a piece of information is placed on each of those k nodes, the overall spread of that information (via word-of-mouth or other methods of influence flow) is maximized. The amount of information spread can be measured using existing information propagation models. Recent studies, which focus on how quickly k high-influential nodes can be found, tend to ignore the overall effect of the information spread. On the other hand some legacy methods, which look at all possible propagation paths to compute a globally optimal target set, present severe scalability challenges in large-scale networks. We present a simple, yet scalable (polynomial time) algorithm that outperforms the existing state-of the-art, and its success does not depend significantly on any kind of tuning parameter. To be more precise, when compared to the existing algorithms, the output set of k nodes produced by our algorithm facilitates higher information spread - in almost all the instances, consistently across the commonly used information propagation models. The original algorithm in this paper, although scalable, can have higher running time than some standard approaches, e.g. simply picking the top k nodes with highest degree or highest Page Rank value. To that end, we provide an optional speedup mechanism that considerably reduces the time complexity while not significantly affecting the quality of results vis-a-vis the full version of our algorithm.

KW - Influence propagation

KW - Social networks

KW - Viral marketing

UR - http://www.scopus.com/inward/record.url?scp=84873179966&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84873179966&partnerID=8YFLogxK

U2 - 10.1109/ICDMW.2012.140

DO - 10.1109/ICDMW.2012.140

M3 - Conference contribution

AN - SCOPUS:84873179966

SN - 9780769549255

T3 - Proceedings - 12th IEEE International Conference on Data Mining Workshops, ICDMW 2012

SP - 258

EP - 265

BT - Proceedings - 12th IEEE International Conference on Data Mining Workshops, ICDMW 2012

T2 - 12th IEEE International Conference on Data Mining Workshops, ICDMW 2012

Y2 - 10 December 2012 through 10 December 2012

ER -