Deakin University
Browse

File(s) under permanent embargo

Geo-social influence spanning maximization

journal contribution
posted on 2017-08-01, 00:00 authored by Jianxin Li, Timos Sellis, J Shane Culpepper, Zhenying He, Chengfei Liu, Junhu Wang
Influence maximization is a recent but well-studied problem which helps identify a small set of users that are most likely to “influence” the maximum number of users in a social network. The problem has attracted a lot of attention as it provides a way to improve marketing, branding, and product adoption. However, existing studies rarely consider the physical locations of the users, but location is an important factor in targeted marketing. In this paper, we propose and investigate the problem of influence maximization in location-aware social networks, or, more generally, Geo-social Influence Spanning Maximization. Given a query q composed of a region R, a regional acceptance rate p, and an integer k as a seed selection budget, our aim is to find the maximum geographic spanning regions (MGSR). We refer to this as the MGSR problem. Our approach differs from previous work as we focus more on identifying the maximum spanning geographical regions within a region R, rather than just the number of activated users in the given network like the traditional influence maximization problem [14]. Our research approach can be effectively used for online marketing campaigns that depend on the physical location of social users. To address the MGSR problem, we first prove NP-Hardness. Next, we present a greedy algorithm with a 1 - 1=e approximation ratio to solve the problem, and further improve the efficiency by developing an upper bounded pruning approach. Then, we propose the OIR*-Tree index, which is a hybrid index combining ordered influential node lists with an R*-tree. We show that our index based approach is significantly more efficient than the greedy algorithm and the upper bounded pruning algorithm, especially when k is large. Finally, we evaluate the performance for all of the proposed approaches using three real datasets.

History

Journal

IEEE transactions on knowledge and data engineering

Volume

29

Pagination

1653-1666

Location

Piscataway, N.J.

ISSN

1041-4347

Language

eng

Publication classification

C1.1 Refereed article in a scholarly journal

Copyright notice

2017, IEEE

Issue

8

Publisher

Institute of Electrical and Electronics Engineers

Usage metrics

    Research Publications

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC