Targeted Influential Nodes Selection in Location-Aware Social Networks
Given a target area and a location-aware social network, the location-aware influence maximization problem aims to find a set of seed users such that the information spread from these users will reach the most users within the target area. We show that the problem is NP-hard and present an approxima...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2018-01-01
|
| Series: | Complexity |
| Online Access: | http://dx.doi.org/10.1155/2018/6101409 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849686831881256960 |
|---|---|
| author | Susu Yang Hui Li Zhongyuan Jiang |
| author_facet | Susu Yang Hui Li Zhongyuan Jiang |
| author_sort | Susu Yang |
| collection | DOAJ |
| description | Given a target area and a location-aware social network, the location-aware influence maximization problem aims to find a set of seed users such that the information spread from these users will reach the most users within the target area. We show that the problem is NP-hard and present an approximate algorithm framework, namely, TarIM-SF, which leverages on a popular sampling method as well as spatial filtering model working on arbitrary polygons. Besides, for the large-scale network we also present a coarsening strategy to further improve the efficiency. We theoretically show that our approximate algorithm can provide a guarantee on the seed quality. Experimental study over three real-world social networks verified the seed quality of our framework, and the coarsening-based algorithm can provide superior efficiency. |
| format | Article |
| id | doaj-art-01208f3ca357404da3bbef2f43fbbda8 |
| institution | DOAJ |
| issn | 1076-2787 1099-0526 |
| language | English |
| publishDate | 2018-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Complexity |
| spelling | doaj-art-01208f3ca357404da3bbef2f43fbbda82025-08-20T03:22:33ZengWileyComplexity1076-27871099-05262018-01-01201810.1155/2018/61014096101409Targeted Influential Nodes Selection in Location-Aware Social NetworksSusu Yang0Hui Li1Zhongyuan Jiang2School of Cyber Engineering, Xidian University, Xi’an 710126, ChinaSchool of Cyber Engineering, Xidian University, Xi’an 710126, ChinaSchool of Cyber Engineering, Xidian University, Xi’an 710126, ChinaGiven a target area and a location-aware social network, the location-aware influence maximization problem aims to find a set of seed users such that the information spread from these users will reach the most users within the target area. We show that the problem is NP-hard and present an approximate algorithm framework, namely, TarIM-SF, which leverages on a popular sampling method as well as spatial filtering model working on arbitrary polygons. Besides, for the large-scale network we also present a coarsening strategy to further improve the efficiency. We theoretically show that our approximate algorithm can provide a guarantee on the seed quality. Experimental study over three real-world social networks verified the seed quality of our framework, and the coarsening-based algorithm can provide superior efficiency.http://dx.doi.org/10.1155/2018/6101409 |
| spellingShingle | Susu Yang Hui Li Zhongyuan Jiang Targeted Influential Nodes Selection in Location-Aware Social Networks Complexity |
| title | Targeted Influential Nodes Selection in Location-Aware Social Networks |
| title_full | Targeted Influential Nodes Selection in Location-Aware Social Networks |
| title_fullStr | Targeted Influential Nodes Selection in Location-Aware Social Networks |
| title_full_unstemmed | Targeted Influential Nodes Selection in Location-Aware Social Networks |
| title_short | Targeted Influential Nodes Selection in Location-Aware Social Networks |
| title_sort | targeted influential nodes selection in location aware social networks |
| url | http://dx.doi.org/10.1155/2018/6101409 |
| work_keys_str_mv | AT susuyang targetedinfluentialnodesselectioninlocationawaresocialnetworks AT huili targetedinfluentialnodesselectioninlocationawaresocialnetworks AT zhongyuanjiang targetedinfluentialnodesselectioninlocationawaresocialnetworks |