Influence Maximization Meets Efficiency and Effectiveness: A Hop-Based Approach
Influence Maximization is an extensively-studied problem that targets at selecting a set of initial seed nodes in the Online Social Networks (OSNs) to spread the influence as widely as possible. However, it remains an open challenge to design fast and accurate algorithms to find solutions in large-s...
Saved in:
Main Authors: | , , |
---|---|
Other Authors: | |
Format: | Conference or Workshop Item |
Language: | English |
Published: |
2017
|
Subjects: | |
Online Access: | https://hdl.handle.net/10356/83550 http://hdl.handle.net/10220/42935 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Nanyang Technological University |
Language: | English |
id |
sg-ntu-dr.10356-83550 |
---|---|
record_format |
dspace |
spelling |
sg-ntu-dr.10356-835502020-11-01T04:43:53Z Influence Maximization Meets Efficiency and Effectiveness: A Hop-Based Approach Tang, Jing Tang, Xueyan Yuan, Junsong School of Computer Science and Engineering School of Electrical and Electronic Engineering Interdisciplinary Graduate School (IGS) 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM) Online social networks Influence maximization Influence Maximization is an extensively-studied problem that targets at selecting a set of initial seed nodes in the Online Social Networks (OSNs) to spread the influence as widely as possible. However, it remains an open challenge to design fast and accurate algorithms to find solutions in large-scale OSNs. Prior Monte-Carlo-simulation-based methods are slow and not scalable, while other heuristic algorithms do not have any theoretical guarantee and they have been shown to produce poor solutions for quite some cases. In this paper, we propose hop-based algorithms that can easily scale to millions of nodes and billions of edges. Unlike previous heuristics, our proposed hop-based approaches can provide certain theoretical guarantees. Experimental evaluations with real OSN datasets demonstrate the efficiency and effectiveness of our algorithms. NRF (Natl Research Foundation, S’pore) MOE (Min. of Education, S’pore) Accepted version 2017-07-19T04:56:32Z 2019-12-06T15:25:25Z 2017-07-19T04:56:32Z 2019-12-06T15:25:25Z 2017 Conference Paper Tang, J., Tang, X., & Yuan, J. (2017). Influence Maximization Meets Efficiency and Effectiveness: A Hop-Based Approach. 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM). https://hdl.handle.net/10356/83550 http://hdl.handle.net/10220/42935 en © 2017 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. 8 p. application/pdf |
institution |
Nanyang Technological University |
building |
NTU Library |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
NTU Library |
collection |
DR-NTU |
language |
English |
topic |
Online social networks Influence maximization |
spellingShingle |
Online social networks Influence maximization Tang, Jing Tang, Xueyan Yuan, Junsong Influence Maximization Meets Efficiency and Effectiveness: A Hop-Based Approach |
description |
Influence Maximization is an extensively-studied problem that targets at selecting a set of initial seed nodes in the Online Social Networks (OSNs) to spread the influence as widely as possible. However, it remains an open challenge to design fast and accurate algorithms to find solutions in large-scale OSNs. Prior Monte-Carlo-simulation-based methods are slow and not scalable, while other heuristic algorithms do not have any theoretical guarantee and they have been shown to produce poor solutions for quite some cases. In this paper, we propose hop-based algorithms that can easily scale to millions of nodes and billions of edges. Unlike previous heuristics, our proposed hop-based approaches can provide certain theoretical guarantees. Experimental evaluations with real OSN datasets demonstrate the efficiency and effectiveness of our algorithms. |
author2 |
School of Computer Science and Engineering |
author_facet |
School of Computer Science and Engineering Tang, Jing Tang, Xueyan Yuan, Junsong |
format |
Conference or Workshop Item |
author |
Tang, Jing Tang, Xueyan Yuan, Junsong |
author_sort |
Tang, Jing |
title |
Influence Maximization Meets Efficiency and Effectiveness: A Hop-Based Approach |
title_short |
Influence Maximization Meets Efficiency and Effectiveness: A Hop-Based Approach |
title_full |
Influence Maximization Meets Efficiency and Effectiveness: A Hop-Based Approach |
title_fullStr |
Influence Maximization Meets Efficiency and Effectiveness: A Hop-Based Approach |
title_full_unstemmed |
Influence Maximization Meets Efficiency and Effectiveness: A Hop-Based Approach |
title_sort |
influence maximization meets efficiency and effectiveness: a hop-based approach |
publishDate |
2017 |
url |
https://hdl.handle.net/10356/83550 http://hdl.handle.net/10220/42935 |
_version_ |
1683494319536734208 |