Influence Spreading Path and Its Application to the Time Constrained Social Influence Maximization Problem and Beyond

Bo Liu, Gao Cong, Yifeng Zeng, Dong Xu, Yeow Meng Chee

    Research output: Contribution to journalArticlepeer-review

    240 Downloads (Pure)

    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.
    Original languageEnglish
    Pages (from-to)1904-1917
    JournalIEEE Transactions on Knowledge and Data Engineering
    Volume26
    Issue number8
    DOIs
    Publication statusPublished - 1 Aug 2014

    Fingerprint Dive into the research topics of 'Influence Spreading Path and Its Application to the Time Constrained Social Influence Maximization Problem and Beyond'. Together they form a unique fingerprint.

    Cite this