TY - JOUR
T1 - INCIM
T2 - A community-based algorithm for influence maximization problem under the linear threshold model
AU - Bozorgi, Arastoo
AU - Haghighi, Hassan
AU - Sadegh Zahedi, Mohammad
AU - Rezvani, Mojtaba
N1 - Publisher Copyright:
© 2016 Elsevier Ltd
PY - 2016/11/1
Y1 - 2016/11/1
N2 - With the proliferation of graph applications in social network analysis, biological networks, WWW and many other areas, a great demand of efficient and scalable algorithms for graph mining is rising. In many applications, finding the most influential nodes in the network is informative for the network analyzers in order to track the spread of information, disease and rumors. The problem of finding the top k influential nodes of a directed graph G=(V,E) such that the influence spread of these nodes will be maximized has long been exposed and many algorithms have been proposed to deal with this problem. Despite the useful characteristics of community structure in social networks, only a few works have studied the role of communities in the spread of influence in social networks. In this paper we propose an efficient algorithm (which has an acceptable response time even for large graphs) for finding the influential nodes in the graph under linear threshold model. We exploit the community structure of graph to find the influential communities, and then find the influence of each node as a combination of its local and global influences. We compare our algorithm with the state-of-the-art methods for influence maximization problem and the results of our experiments on real world datasets show that our approach outperforms the other ones in the quality of outputted influential nodes while still has acceptable running time and memory usage for large graphs.
AB - With the proliferation of graph applications in social network analysis, biological networks, WWW and many other areas, a great demand of efficient and scalable algorithms for graph mining is rising. In many applications, finding the most influential nodes in the network is informative for the network analyzers in order to track the spread of information, disease and rumors. The problem of finding the top k influential nodes of a directed graph G=(V,E) such that the influence spread of these nodes will be maximized has long been exposed and many algorithms have been proposed to deal with this problem. Despite the useful characteristics of community structure in social networks, only a few works have studied the role of communities in the spread of influence in social networks. In this paper we propose an efficient algorithm (which has an acceptable response time even for large graphs) for finding the influential nodes in the graph under linear threshold model. We exploit the community structure of graph to find the influential communities, and then find the influence of each node as a combination of its local and global influences. We compare our algorithm with the state-of-the-art methods for influence maximization problem and the results of our experiments on real world datasets show that our approach outperforms the other ones in the quality of outputted influential nodes while still has acceptable running time and memory usage for large graphs.
KW - Community detection
KW - Influence maximization
KW - Influence spread
KW - Linear threshold model
KW - Social network
UR - http://www.scopus.com/inward/record.url?scp=84969930005&partnerID=8YFLogxK
U2 - 10.1016/j.ipm.2016.05.006
DO - 10.1016/j.ipm.2016.05.006
M3 - Article
SN - 0306-4573
VL - 52
SP - 1188
EP - 1199
JO - Information Processing and Management
JF - Information Processing and Management
IS - 6
ER -