A self-stabilizing algorithm for finding a minimal positive influence dominating set in social networks
Paper
Paper/Presentation Title | A self-stabilizing algorithm for finding a minimal positive influence dominating set in social networks |
---|---|
Presentation Type | Paper |
Authors | Wang, Guangyuan (Author), Wang, Hua (Author), Tao, Xiaohui (Author) and Zhang, Ji (Author) |
Editors | Wang, Hua and Zhang, Rui |
Journal or Proceedings Title | Conferences in Research and Practice in Information Technology (CRPIT) |
ERA Conference ID | 42492 |
Journal Citation | 137, pp. 93-100 |
Number of Pages | 8 |
Year | 2013 |
Place of Publication | Sydney, Australia |
ISBN | 9781921770227 |
Web Address (URL) of Paper | http://crpit.com/abstracts/CRPITV137Wang.html |
Conference/Event | 24th Australasian Database Conference (ADC 2013) |
Australasian Database Conference | |
Event Details | Australasian Database Conference ADC Rank B B B B B B B B B B B B B B B B B B B B |
Event Details | 24th Australasian Database Conference (ADC 2013) Event Date 29 Jan 2013 to end of 01 Feb 2013 Event Location Adelaide, Australia |
Abstract | Online social network has developed significantly in recent years. Most of current research has utilized the property of online social network to spread information and ideas. Motivated by applications in social networks (such as alcohol intervention strategies), a variation of the dominating set called a positive influence dominating set (PIDS) has been studied in the literature. However, the existing work all focused on greedy algorithms for the PIDS problem with different approximation ratios, which are limited to find approximate solutions to PIDS in large networks. In order to select a minimal PIDS (MPIDS) in large social networks, we first present a self-stabilizing algorithm for the MPIDS problem in this paper, which can find a MPIDS in an arbitrary network graph without any isolated node. It is assumed that the nodes in the proposed algorithm have globally unique identifiers, and the algorithm works under a central daemon. We further prove that the worst case convergence time of the algorithm from any arbitrary initial state is O(n2 ) steps where n is the number of nodes in the network. |
Keywords | positive influence dominating set; PIDS |
ANZSRC Field of Research 2020 | 460806. Human-computer interaction |
469999. Other information and computing sciences not elsewhere classified | |
Public Notes | File reproduced in accordance with the copyright policy of the publisher/author. |
Byline Affiliations | Department of Mathematics and Computing |
Institution of Origin | University of Southern Queensland |
https://research.usq.edu.au/item/q24xx/a-self-stabilizing-algorithm-for-finding-a-minimal-positive-influence-dominating-set-in-social-networks
Download files
1847
total views176
total downloads3
views this month1
downloads this month