Loading...
Please wait, while we are loading the content...
Similar Documents
Community-based greedy algorithm for mining top-k influential nodes in mobile social networks.
| Content Provider | CiteSeerX |
|---|---|
| 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 fundamen-tal issue to find a subset of influential individuals in a mobile social network such that targeting them initially (e.g. to adopt a new prod-uct) 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 ac-count information diffusion; and 2) a dynamic programming algo-rithm for selecting communities to find influential nodes. We also provide provable approximation guarantees for our algorithm. Em-pirical 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. |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Mobile Social Network Community-based Greedy Algorithm Mining Top-k Influential Node Top-k Influential Node Greedy Algorithm Provable Approximation Guarantee Influential Node Approximate Algorithm Wireless Technology Fundamen-tal Issue Ac-count Information Diffusion New Product Mobile Social Network System Em-pirical Study Essential Role Large Mobile Network Mobile Device Good Approximation Social Network New Prod-uct New Algorithm Dynamic Programming Algo-rithm Influential Individual State-of-the-art Greedy Algorithm |
| Content Type | Text |
| Resource Type | Article |
