微信服务号

微信订阅号

2025年5月10日 12:41 星期六
首页 > 过刊浏览>2014年第25卷第12期 >2837-2851. DOI:10.13328/j.cnki.jos.004723
PDF HTML阅读 XML下载 导出引用 引用提醒
面向社交网络信息源定位的观察点部署方法
作者:
基金项目:

国家自然科学基金(60903009,71272216,61073062,61100090);中央高校基本科研业务费(120404011,120804001,120604003);黑龙江省普通高等学校青年学术骨干支持计划(1253G017)


Observer Deployment Method for Locating the Information Source in Social Network
Author:
  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [37]
    • |
  • 相似文献 [20]
    • | | |
  • 文章评论
    摘要:

    准确地定位社交网络上的信息扩散源点,对于网络信息扩散控制具有重要的现实意义.现有的一种可行方法是通过在网络中观察点搜集的过程信息对扩散源进行定位,定位准确率与观察点的选择紧密相关.针对网络中的信息扩散源定位问题,提出了一种网络观察点优化部署方法.考虑单信息源的信息扩散过程,首先分析了特定信息源定位准确率与观察点部署位置之间的关系,以此为基础,发现了与任意信息源定位准确率相关的关键因素.提出基于r覆盖率的观察点部署策略,以观察点集合的r覆盖率作为目标函数,实现了r覆盖率优先观察点选取算法.在模型网络与实际网络上进行了实验,验证了该方法的有效性.提出的观察点部署策略对于网络谣言、计算机病毒的控制具有重要意义.

    Abstract:

    Locating information source accurately is important for controlling its diffusion on the social network. In previous studies, a feasible way is locating the source using process information collected by the observers. Thus, the accuracy rate is closely related to the observer positions. In this paper, an optimal deployment method for observer positions is proposed. Considering the information diffusion process for single source, it firstly analyzes the relationship between the accuracy rate for locating a specified source and the positions of observers. Based on the relationship, it finds a key factor which is related to the accuracy rate of locating any source. It then suggests a method to deploy the observer positions based on r-coverage rate. It chooses the r-coverage rate of the observers as the objective function to implement the r-coverage rate first observer selection algorithm. The proposed method is tested on model and real networks respectively. Results show that the proposed method is effective. The observer deployment method is significant in controlling internet rumors and computer virus.

    参考文献
    [1] Zinoviev D, Duong V, Zhang HG. A game theoretical approach to modeling information dissemination in social networks. In: Proc. of the IMCCIC. 2010. 407-412.
    [2] Zinoviev D, Duong V. A game theoretical approach to broadcast information diffusion in social networks. In: Proc. of the 44th Annual Simulation Symp. Society for Computer Simulation Int'l, 2011. 47-52.
    [3] Easley D, Kleinberg J. Networks, crowds, and markets: Reasoning about a highly connected world. Cambridge University Press, 2010,6(1):6.1. [doi: 10.1017/S0266466609990685]
    [4] Pastor-Satorras R, Vespignani A. Epidemic dynamics and endemic states in complex networks. Physical Review E, 2001,63(6):19. [doi: 10.1103/PhysRevE.63.066117]
    [5] Pastor-Satorras R, Vespignani A. Epidemic dynamics in finite size scale-free networks. Physical Review E, 2002,65(3):14. [doi: 10.1103/PhysRevE.65.035108]
    [6] Jagatic T, Johnson NA, Jakobsson M, Menczer F. Social phishing. Communications of the ACM, 2007,50(10):94-100. [doi: 10.1145/1290958.1290968]
    [7] Chen W, Wang C, Wang YJ. Scalable influence maximization for prevalent viral marketing in large-scale social networks. In: Proc. of the 16th ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining. ACM Press, 2010. 1029-1038. [doi: 10.1145/ 1835804.1835934]
    [8] Chen W, Wang YJ, Yang SY. Efficient influence maximization in social networks. In: Proc. of the 15th ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining. ACM Press, 2009. 199-208. [doi: 10.1145/1557019.1557047]
    [9] Kwak H, Lee C, Park H, Moon S. What is Twitter, a social network or a news media. In: Proc. of the 19th Int'l Conf. on World Wide Web. ACM Press, 2010. 591-600. [doi: 10.1145/1772690.1772751]
    [10] Granovetter M. Threshold models of collective behavior. American Journal of Sociology, 1978,83(6):1420-1443.
    [11] Goldenberg J, Libai B, Muller E. Talk of the network: A complex systems look at the underlying process of word-of-mouth. Marketing Letters, 2001,12(3):211-223.
    [12] Cha M, Mislove A, Adams B, Gummadi KP. Characterizing social cascades in flickr. In: Proc. of the 1st Workshop on Online Social Networks. ACM Press, 2008. 13-18. [doi: 10.1145/1397735.1397739]
    [13] Mislove A, Marcon M, Gummadi KP, Druschel P, Bhattacharjee B. Measurement and analysis of online social networks. In: Proc. of the 7th ACM SIGCOMM Conf. on Internet Measurement. ACM Press, 2007. 29-42. [doi: 10.1145/1298306.1298311]
    [14] Richardson M, Domingos P. Mining knowledge-sharing sites for viral marketing. In: Proc. of the 8th ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining. ACM Press, 2002. 61-70. [doi: 10.1145/775047.775057]
    [15] Kempe D, Kleinberg J, Tardos É. Maximizing the spread of influence through a social network. In: Proc. of the 9th ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining. ACM Press, 2003. 137-146. [doi: 10.1145/956750.956769]
    [16] Budak C, Agrawal D, El Abbadi AE. Limiting the spread of misinformation in social networks. In: Proc. of the 20th Int'l Conf. on World Wide Web. ACM Press, 2011. 665-674. [doi: 10.1145/1963405.1963499]
    [17] Wang Y, Cong G, Song GJ, Xie KQ. Community-Based greedy algorithm for mining top-k influential nodes in mobile social networks. In: Proc. of the 16th ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining. ACM Press, 2010. 1039-1048. [doi: 10.1145/1835804.1835935]
    [18] Shah D, Zaman T. Detecting sources of computer viruses in networks: Theory and experiment. ACM SIGMETRICS Performance Evaluation Review, 2010,38(1):203-214. [doi: 10.1145/1811099.1811063]
    [19] Lokhov AY, Mézard M, Ohta H, Zdeborova L. Inferring the origin of an epidemy with dynamic message-passing algorithm. Eprint arXiv: 1303.5315. 2013.
    [20] Prakash BA, Vreeken J, Faloutsos C. Spotting culprits in epidemics: How many and which ones. ICDM, 2012,12:11-20.
    [21] Pinto PC, Thiran P, Vetterli M. Locating the source of diffusion in large-scale networks. Physical Review Letters, 2012,109(6): 068702. [doi: 10.1103/PhysRevLett.109.068702]
    [22] Agrawal D, Budak C, Abbadi AE. Information diffusion in social networks: Observing and influencing societal interests. Proc. of the VLDB Endowment, 2011,4(12):1-5.
    [23] Weng JS, Lim EP, Jiang J, He Q. Twitterrank: Finding topic-sensitive influential Twitterers. In: Proc. of the 3rd ACM Int'l Conf. on Web Search and Data Mining. ACM Press, 2010. 261-270. [doi: 10.1145/1718487.1718520]
    [24] Budak C, Agrawal D, El Abbadi AE. Structural trend analysis for online social networks. Proc. of the VLDB Endowment, 2011, 4(10):646-656.
    [25] Zhu K, Ying L. Information source detection in the SIR model: A sample path based approach. In: Proc. of the Information Theory and Applications Workshop (ITA). IEEE, 2013. 1-9. [doi: 10.1109/ITA.2013.6502991]
    [26] Brockmann D, Helbing D. The hidden geometry of complex, network-driven contagion phenomena. Science, 2013,342(6164): 1337-1342. [doi: 10.1126/science.1245200]
    [27] Ghosh R, Lerman K. Predicting influential users in online social networksp. In: Proc. of the 4th KDD Workshop on Social Network Analysis. Washington, 2010
    [28] Freeman LC. Centrality in social networks conceptual clarification. Social Networks, 1979,1(3):215-239.
    [29] Pastor-Satorras R, Vespignani A. Epidemic spreading in scale-free networks. Physical Review Letters, 2001,86:3200-3203.
    [30] Newman MEJ. A measure of betweenness centrality based on random walks. Social Networks, 2005,27(1):39-54.
    [31] Freeman LC. A Set of Measures of Centrality based on Betweenness. Sociometry, 1977. 35-41.
    [32] Holland PW, Leinhardt S. Transitivity in structural models of small groups. Comparative Group Studies, 1971,2(2):107-124.
    [33] Kitsak M, Gallos LK, Havlin S, Liljeros F, Muchnik L, Stanley HE, Makse HA. Identification of influential spreaders in complex networks. Nature Physics, 2010,6(11):888-893.
    [34] Lemke CE, Salkin HM, Spielberg K. Set covering by single-branch enumeration with linear-programming subproblems. Operations Research, 1971,19(4):998-1022.
    [35] Kearns MJ. The Computational Complexity of Machine Learning. Cambridge: MIT Press, 1990. 68-73.
    [36] Adamic L, Glance N. The political blogosphere and the 2004 US election: divided they blog. In: Proc. of the 3rd Int'l Workshop on Link Discovery. ACM Press, 2005. 36-43. [doi: 10.1145/1134271.1134277]
    [37] Opsahl T, Panzarasa P. Clustering in weighted networks. Social Networks, 2009,31(2):155-163. [doi: 10.1016/j.socnet.2009.02. 002]
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

张聿博,张锡哲,张斌.面向社交网络信息源定位的观察点部署方法.软件学报,2014,25(12):2837-2851

复制
分享
文章指标
  • 点击次数:6216
  • 下载次数: 8068
  • HTML阅读次数: 2579
  • 引用次数: 0
历史
  • 收稿日期:2014-04-17
  • 最后修改日期:2014-08-21
  • 在线发布日期: 2014-12-04
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会CCF数字图书馆Int'l J of Softw Info计算机系统应用
您是第19919641位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号