2010 CommunitybasedGreedyAlgorithmfo

• (Wang et al., 2010) ⇒ Yu Wang, Gao Cong, Guojie Song, and Kunqing Xie. (2010). “Community-based Greedy Algorithm for Mining Top-K Influential Nodes in Mobile Social Networks.” In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2010). doi:10.1145/1835804.1835935

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%22Community-based+greedy+algorithm+for+mining+top-K+influential+nodes+in+mobile+social+networks%22+2010
• http://portal.acm.org/citation.cfm?id=1835935&preflayout=flat#citedby

Quotes

Abstract

With the proliferation of mobile devices and wireless technologies, mobile social network systems are increasingly available. A mobile social network plays an essential role as the spread of information and influence in the form of “word-of-mouth”. It is a fundamental issue to find a subset of influential individuals in a mobile social network such that targeting them initially (e.g. to adopt a new product) will maximize the spread of the influence (further adoptions of the new product). The problem of finding the most influential nodes is unfortunately NP-hard. It has been shown that a Greedy algorithm with provable approximation guarantees can give good approximation; However, it is computationally expensive, if not prohibitive, to run the greedy algorithm on a large mobile network.

In this paper we propose a new algorithm called Community-based Greedy algorithm for mining top-K influential nodes. The proposed algorithm encompasses two components: 1) an algorithm for detecting communities in a social network by taking into account information diffusion; and 2) a dynamic programming algorithm for selecting communities to find influential nodes. We also provide provable approximation guarantees for our algorithm. Empirical studies on a large real-world mobile social network show that our algorithm is more than an order of magnitudes faster than the state-of-the-art Greedy algorithm for finding top-K influential nodes and the error of our approximate algorithm is small.

References

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2010 CommunitybasedGreedyAlgorithmfo	Yu Wang Gao Cong Guojie Song Kunqing Xie			Community-based Greedy Algorithm for Mining Top-K Influential Nodes in Mobile Social Networks		KDD-2010 Proceedings		10.1145/1835804.1835935		2010