{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,2,7]],"date-time":"2023-02-07T19:55:28Z","timestamp":1675799728280},"reference-count":6,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2010,3]]},"abstract":"<jats:p> Social networks are attracting more attention from both industry and academia. Prior works on social networks focus on analyzing their roles in information propagation and decision making. However, few of these works consider the latency of information propagation, which is an essential issue especially in time-critical scenarios in social networks. In this paper, we introduce a new problem called FAST INFORMATION PROPAGATION PROBLEM, which is an optimization problem to identify the minimum set of influential nodes that could influence the whole network within a given latency bound d. We show our complexity result on this problem in the deterministic threshold models and present a greedy hill-climbing algorithm as the solution. For the d = 1 case, we prove that under the majority threshold model, this approximation algorithm has a performance ratio of H(\u0394 + 1) - 1 + \u2308 \u0394\/2\u2309. Extensive experiments are conducted on a large collaboration network and the results show that our approximation algorithm outperforms the node-selection heuristics, which utilize the well-known approaches based on the node centrality in the social network analysis. <\/jats:p>","DOI":"10.1142\/s1793830910000528","type":"journal-article","created":{"date-parts":[[2010,4,20]],"date-time":"2010-04-20T05:35:00Z","timestamp":1271741700000},"page":"125-141","source":"Crossref","is-referenced-by-count":10,"title":["FAST INFORMATION PROPAGATION IN SOCIAL NETWORKS"],"prefix":"10.1142","volume":"02","author":[{"given":"FENG","family":"ZOU","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Texas at Dallas, Richardson, TX, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JAMES K.","family":"WILLSON","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Texas at Dallas, Richardson, TX, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ZHAO","family":"ZHANG","sequence":"additional","affiliation":[{"name":"College of Mathematics and System Sciences, Xinjiang University, Urumqi, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"WEILI","family":"WU","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Texas at Dallas, Richardson, TX, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2012,4,5]]},"reference":[{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1086\/226707"},{"key":"rf11","author":"Goldenberg J.","journal-title":"Academy of Marketing Science Review"},{"key":"rf13","volume-title":"Computers and Intractability; A Guide to the Theory of NP-Completeness","author":"Garey M.","year":"1979"},{"key":"rf14","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"2001"},{"key":"rf17","volume-title":"Social Network Analysis: A Handbook","author":"Scott J. P.","year":"2000"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511815478"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830910000528","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T21:23:21Z","timestamp":1565126601000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830910000528"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,3]]},"references-count":6,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2012,4,5]]},"published-print":{"date-parts":[[2010,3]]}},"alternative-id":["10.1142\/S1793830910000528"],"URL":"https:\/\/doi.org\/10.1142\/s1793830910000528","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,3]]}}}