Title | ||
---|---|---|
Influence Spreading Path and Its Application to the Time Constrained Social Influence Maximization Problem and Beyond |
Abstract | ||
---|---|---|
Influence maximization is a fundamental research problem in social networks. Viral marketing, one of its applications, is to get a small number of users to adopt a product, which subsequently triggers a large cascade of further adoptions by utilizing “Word-of-Mouth” effect in social networks. Time plays an important role in the influence spread from one user to another and the time needed for a user to influence another varies. In this paper, we propose the time constrained influence maximization problem. We show that the problem is NP-hard, and prove the monotonicity and submodularity of the time constrained influence spread function. Based on this, we develop a greedy algorithm. To improve the algorithm scalability, we propose the concept of Influence Spreading Path in social networks and develop a set of new algorithms for the time constrained influence maximization problem. We further parallelize the algorithms for achieving more time savings. Additionally, we generalize the proposed algorithms for the conventional influence maximization problem without time constraints. All of the algorithms are evaluated over four public available datasets. The experimental results demonstrate the efficiency and effectiveness of the algorithms for both conventional influence maximization problem and its time constrained version. |
Year | DOI | Venue |
---|---|---|
2014 | 10.1109/TKDE.2013.106 | IEEE Trans. Knowl. Data Eng. |
Keywords | Field | DocType |
algorithm scalability,optimisation,time constrained,large scale,social network,social networks,np-hard problem,influence spreading path,time constrained social influence maximization problem,marketing data processing,greedy algorithm,computational complexity,influence maximization,greedy algorithms,time constrained influence spread function,viral marketing,social networking (online),word-of-mouth effect | Small number,Monotonic function,Mathematical optimization,Viral marketing,Social network,Computer science,Greedy algorithm,Social influence,Artificial intelligence,Maximization,Machine learning,Scalability | Journal |
Volume | Issue | ISSN |
26 | 8 | 1041-4347 |
Citations | PageRank | References |
24 | 0.72 | 16 |
Authors | ||
5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Bo Liu | 1 | 24 | 0.72 |
gao cong | 2 | 4086 | 169.93 |
Yifeng Zeng | 3 | 415 | 43.27 |
Dong Xu | 4 | 7616 | 291.96 |
Yeow Meng Chee | 5 | 593 | 62.01 |