Influence maximization algorithm using markov clustering

Chungrim Kim, Sangkeun Lee, Sungchan Park, Sang Goo Lee

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

6 Scopus citations

Abstract

Social Network Services are known as a effective marketing platform in that the customers trust the advertisement provided by their friends and neighbors. Viral Marketing is a marketing technique that uses the pre-constructed social networks to perform maketing with small cost while maximizing the spread. Therefore, which seed user to select is the primary concern in viral marketing. Influence maximization problem is a well known problem to find the top-k seed users who can maximize the spread of information in a social network. Since obtaining the global optimal solution for the influence maximization problem is proven to be NP-Hard, many greedy as well as heuristic approach has been researched. However, greedy approaches take to much time to obtain the seed node, whereas the heuristic approaches show poor performance. To remedy such problems, we exploit the community structures in the social network to enhance the performance of the heuristic approaches. We perform markov clustering to find the natural communities in the social network and consider the most influential user in the community as the candidate for the top-k seeds. Also, we propose a novel attractor identification algorithm that finds the influential nodes in the community with reduced runtime, and 3 new hybrid approaches for influence maximization problem. Experiments show that the proposed algorithms are more scalable than the greedy approaches, whereas the influence spread obtained by those outperforms the heuristic approaches.

Original languageEnglish
Title of host publicationDatabase Systems for Advanced Applications - 18th International Conference, DASFAA 2013 International Workshops
Subtitle of host publicationBDMA, SNSM, SeCoP, Proceedings
Pages112-126
Number of pages15
DOIs
StatePublished - 2013
Externally publishedYes
Event18th International Conference on Database Systems for Advanced Applications, DASFAA 2013 - Wuhan, China
Duration: Apr 22 2013Apr 25 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7827 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference18th International Conference on Database Systems for Advanced Applications, DASFAA 2013
Country/TerritoryChina
CityWuhan
Period04/22/1304/25/13

Keywords

  • Influence maximization
  • Markov clustering

Fingerprint

Dive into the research topics of 'Influence maximization algorithm using markov clustering'. Together they form a unique fingerprint.

Cite this