Identifying source of an information in complex networks with limited observation nodes
详细信息 查看官网全文
- 英文论文题名：Identifying source of an information in complex networks with limited observation nodes
- 论文作者：Xindai Lu ; Yiyang Yao ; Yinzuo Zhou
- 英文论文作者：Xindai Lu ; Yiyang Yao ; Yinzuo Zhou ; State Grid Zhejiang Electric Power Research Institute ; State Grid Zhejiang Electric Power Company Information & Telecommunication Branch ; Alibaba Research Center for Complexity Sciences ; Hangzhou Normal University
- 年：2017
- 作者机构：State Grid Zhejiang Electric Power Research Institute;State Grid Zhejiang Electric Power Company Information & Telecommunication Branch;Alibaba Research Center for Complexity Sciences,Hangzhou Normal University;
- 英文论文关键词：Source Nodes ; Observation Nodes ; SI Model
- 会议召开时间：2017-07-26
- 会议录名称：第36届中国控制会议论文集（A）
- 英文会议录名称：Proceedings of the 36th Chinese Control Conference（A）
- 语种：英文
- 分类号：O157.5
- 学会代码：KZLL
- 会议名称：第36届中国控制会议
- 会议地点：中国辽宁大连
- 主办单位：中国自动化学会控制理论专业委员会
- 学会名称：中国自动化学会控制理论专业委员会
- 页数：6
- 文件大小：173k
- 原文格式：D
- 会议级别：全国
摘要
A rumor spreading in a social network or a disease propagating in a community can be described by a contact network whose nodes are persons or centers of contagion and links heterogeneous relations among them. Suppose that a rumor or a disease originating from a single source among a set of suspects spreads in a network, how to root out this rumor/disease source? This problem is important and challenging in different contexts of computer or social networks, which is made more difficult in many applications where we have access only to a limited set of observations. We study the problem of estimating the origin of a rumor/epidemic outbreak: given a contact network and a snapshot of epidemic spread at a certain time, determine the infection source. Assuming that the epidemic spread follows the usual susceptible-infected(SI) model, we introduce an inference algorithm based on sparsely placed observers. We present a strategy and show that it leads to significant improvement of performance compared to existing approaches. Our analysis sheds insight into the behavior of the rumor/epidemic spreading process not only in the local particular regime but also for the whole general regime.
A rumor spreading in a social network or a disease propagating in a community can be described by a contact network whose nodes are persons or centers of contagion and links heterogeneous relations among them. Suppose that a rumor or a disease originating from a single source among a set of suspects spreads in a network, how to root out this rumor/disease source? This problem is important and challenging in different contexts of computer or social networks, which is made more difficult in many applications where we have access only to a limited set of observations. We study the problem of estimating the origin of a rumor/epidemic outbreak: given a contact network and a snapshot of epidemic spread at a certain time, determine the infection source. Assuming that the epidemic spread follows the usual susceptible-infected(SI) model, we introduce an inference algorithm based on sparsely placed observers. We present a strategy and show that it leads to significant improvement of performance compared to existing approaches. Our analysis sheds insight into the behavior of the rumor/epidemic spreading process not only in the local particular regime but also for the whole general regime.
A rumor spreading in a social network or a disease propagating in a community can be described by a contact network whose nodes are persons or centers of contagion and links heterogeneous relations among them. Suppose that a rumor or a disease originating from a single source among a set of suspects spreads in a network, how to root out this rumor/disease source? This problem is important and challenging in different contexts of computer or social networks, which is made more difficult in many applications where we have access only to a limited set of observations. We study the problem of estimating the origin of a rumor/epidemic outbreak: given a contact network and a snapshot of epidemic spread at a certain time, determine the infection source. Assuming that the epidemic spread follows the usual susceptible-infected(SI) model, we introduce an inference algorithm based on sparsely placed observers. We present a strategy and show that it leads to significant improvement of performance compared to existing approaches. Our analysis sheds insight into the behavior of the rumor/epidemic spreading process not only in the local particular regime but also for the whole general regime.
引文
[1]B.Viswanath,A.Mislove,M.Cha,and K.P.Gummadi,On the evolution of user interaction in Facebook,in Proc.2nd ACM Workshop on Online Social Networks,2009:37–42.
[2]R.Kumar,J.Novak,and A.Tomkins,Structure and evolution of online social networks,in Link Mining:Models,Algorithms,and Applications,Springer New York,2010:337–357.
[3]http://googleblog.blogspot.sg/2012/12/googlecommunities-and-photos.html
[4]http://investor.fb.com/releasedetail.cfm?Release ID=780093
[5]R.Alcarria,T.Robles,and G.Camarillo,Towards the convergence between IMS and social networks,in Proc.6th International Conference on Wireless and Mobile Communications,2010.
[6]A.-L.Barabasi,R.Albert,Emergence of scaling in random networks,Science,286:509,1999.
[7]Z.Liu,B.Hu,Epidemic spreading in community networks,Europhys.Lett.,72:315,2005.
[8]Y.Zhou,Z.Liu,J.Zhou,Periodic wave of epidemic spreading in community networks,Chin.Phys.Lett.,24:581,2007.
[9]J.Zhou,Z.Liu,Epidemic spreading in communities with mobile agents,Physica A,388:1228,2009.
[10]J.Zhou,G.Xiao,S.A.Cheong,X.Fu,L.Wong,S.Ma,T.H.Cheng,Epidemic reemergence in adaptive complex networks,Phys.Rev.E,85:036107,2012.
[11]J.Zhou,N.Chung,L.Chew,C.Lai,Epidemic spreading induced by diversity of agents mobility,Phys.Rev.E,86:026115,2012.
[12]J.Zhou,G.Xiao,G.Chen,Link-based formalism for time evolution of adaptive networks,Phys.Rev.E,88:032808,2013.
[13]Y.Zhou,Y.Xia,Epidemic spreading on weighted adaptive networks,Physica A,399:16,2014.
[14]Z.Liu,Y.-C.Lai,N.Ye,P.Dasgupta,Connectivity distribution and attack tolerance of general networks with both preferential and random attachments,Physics Letters A,303:337C-344,2002.
[15]G.Kossinets and D.J.Watts,Empirical analysis of an evolving social network,Science,311(5757):88–90,2006.
[16]http://www.techinasia.com/china-tweeting-rumorsland-years-jailor-worse/
[17]D.Kempe,J.Kleinberg,and E.Tardos,Maximizing the spread of influence through a social network,in Proc.9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2003:137–146.
[18]J.Leskovec,L.A.Adamic,and B.A.Huberman,The dynamics of viral marketing,ACM Trans.Web,1(1):Article No.5,2007.
[19]W.Chen,Y.Wang,and S.Yang,Effi cient influence maximization in social networks,in Proc.15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2009:199–208.
[20]C.Moore and M.E.J.Newman,Epidemics and percolation in small-world networks,Phys.Rev.E,61:5678,2000.
[21]R.P.Satorras,and A.Vespignani,Epidemic spreading in scale-free networks,Phys.Rev.Lett.,86:3200,2001.
[22]M.Kuperman,and G.Abramson,Small world effect in an epidemiological model,Phys.Rev.Lett.,86:2909,2001.
[23]M.E.J.Newman,Spread of epidemic disease on networks,Phys.Rev.E,66:016128,2002.
[24]A.Ganesh,L.Massoulie,and D.Towsley,Proceedings of IEEE Conference on Computer Communication,IEEE,New York,2005:1455.
[25]E.Bertuzzo,S.Azaele,A.Maritan,M.Gatto,I.Rodriguez-Iturbe,and A.Rinaldo,On the space-time evolution of a cholera epidemic,Water Resour.Res.,44:W01424,2008.
[26]P.G.Lind,L.R.da Silva,J.S.Andrade,Jr.,H.J.Herrmann,Spreading gossip in social networks,Phys.Rev.E,76:036117,2007.
[27]P.C.Pinto,P.Thiran,and M.Vetterli,Locating the source of diffusion in large-scale networks,Phys.Rev.Lett.,109:068702,2012.
[28]D.Shah and T.Zaman,Rumors in a network:Who’s the culprit?,IEEE Trans.Inf.Theory,57(8):5163–5181,2011.
[29]W.Luo,W.P.Tay,and M.Leng,Identifying infection sources and regions in large networks,IEEE Trans.Signal Process.,61(11):2850–2865,2013.
[30]W.Dong,W.Zhang,and C.W.Tan,Rooting out the rumor culprit from suspects,Information Theory Proceedings(ISIT),2013 IEEE International Symposium on Information Theory,2013.
[31]K.Zhu and L.Ying,Information source detection in the SIR model:a sample path based approach,in Information Theory and Applications Workshop,2013.
[32]W.Luo and W.P.Tay,Finding an infection source under the SIS model,Acoustics,Speech and Signal Processing(ICASSP),2013 IEEE International Conference on Acoustics,Speech and Signal Processing,2013.
[33]Y.Zhang,Z.Wang,and C.Xia,Identifying key users for targeted marketing by mining online social network,in Proc.24th IEEE International Conference on Advanced Information Networking and Applications Workshops,2010.
[34]M.Gomez Rodriguez,J.Leskovec,and A.Krause,Inferring networks of diffusion and influence,in Proc.16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2010.
[35]E.Bakshy,J.M.Hofman,W.A.Mason,and D.J.Watts,Everyone’s an influencer:quantifying influence on Twitter,in Proc.4th ACM International Conference on Web Search and Data Mining,2011.
[36]A.-L.Barabasi,R.Albert,H.Jeong,Mean-fi eld theory for scale-free random networks,Physica A,272(1-2):173-187,1999;
[37]A.-L.Barabasi,R.Albert,H.Jeong,Scale-free characteristics of random networks:the topology of the worldwide web,Physica A,281(1-4):69–77,2000.
[38]P.L.Krapivsky,S.Redner,F.Leyvraz,Connectivity of growing random networks,Phys.Rev.Lett.,85:4629,2000;
[39]Z.Liu,Y.-C.Lai,N.Ye,Statistical properties and attack tolerance of growing networks with algebraic preferential attachment,Phys.Rev.E,66:036112,2002.
[2]R.Kumar,J.Novak,and A.Tomkins,Structure and evolution of online social networks,in Link Mining:Models,Algorithms,and Applications,Springer New York,2010:337–357.
[3]http://googleblog.blogspot.sg/2012/12/googlecommunities-and-photos.html
[4]http://investor.fb.com/releasedetail.cfm?Release ID=780093
[5]R.Alcarria,T.Robles,and G.Camarillo,Towards the convergence between IMS and social networks,in Proc.6th International Conference on Wireless and Mobile Communications,2010.
[6]A.-L.Barabasi,R.Albert,Emergence of scaling in random networks,Science,286:509,1999.
[7]Z.Liu,B.Hu,Epidemic spreading in community networks,Europhys.Lett.,72:315,2005.
[8]Y.Zhou,Z.Liu,J.Zhou,Periodic wave of epidemic spreading in community networks,Chin.Phys.Lett.,24:581,2007.
[9]J.Zhou,Z.Liu,Epidemic spreading in communities with mobile agents,Physica A,388:1228,2009.
[10]J.Zhou,G.Xiao,S.A.Cheong,X.Fu,L.Wong,S.Ma,T.H.Cheng,Epidemic reemergence in adaptive complex networks,Phys.Rev.E,85:036107,2012.
[11]J.Zhou,N.Chung,L.Chew,C.Lai,Epidemic spreading induced by diversity of agents mobility,Phys.Rev.E,86:026115,2012.
[12]J.Zhou,G.Xiao,G.Chen,Link-based formalism for time evolution of adaptive networks,Phys.Rev.E,88:032808,2013.
[13]Y.Zhou,Y.Xia,Epidemic spreading on weighted adaptive networks,Physica A,399:16,2014.
[14]Z.Liu,Y.-C.Lai,N.Ye,P.Dasgupta,Connectivity distribution and attack tolerance of general networks with both preferential and random attachments,Physics Letters A,303:337C-344,2002.
[15]G.Kossinets and D.J.Watts,Empirical analysis of an evolving social network,Science,311(5757):88–90,2006.
[16]http://www.techinasia.com/china-tweeting-rumorsland-years-jailor-worse/
[17]D.Kempe,J.Kleinberg,and E.Tardos,Maximizing the spread of influence through a social network,in Proc.9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2003:137–146.
[18]J.Leskovec,L.A.Adamic,and B.A.Huberman,The dynamics of viral marketing,ACM Trans.Web,1(1):Article No.5,2007.
[19]W.Chen,Y.Wang,and S.Yang,Effi cient influence maximization in social networks,in Proc.15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2009:199–208.
[20]C.Moore and M.E.J.Newman,Epidemics and percolation in small-world networks,Phys.Rev.E,61:5678,2000.
[21]R.P.Satorras,and A.Vespignani,Epidemic spreading in scale-free networks,Phys.Rev.Lett.,86:3200,2001.
[22]M.Kuperman,and G.Abramson,Small world effect in an epidemiological model,Phys.Rev.Lett.,86:2909,2001.
[23]M.E.J.Newman,Spread of epidemic disease on networks,Phys.Rev.E,66:016128,2002.
[24]A.Ganesh,L.Massoulie,and D.Towsley,Proceedings of IEEE Conference on Computer Communication,IEEE,New York,2005:1455.
[25]E.Bertuzzo,S.Azaele,A.Maritan,M.Gatto,I.Rodriguez-Iturbe,and A.Rinaldo,On the space-time evolution of a cholera epidemic,Water Resour.Res.,44:W01424,2008.
[26]P.G.Lind,L.R.da Silva,J.S.Andrade,Jr.,H.J.Herrmann,Spreading gossip in social networks,Phys.Rev.E,76:036117,2007.
[27]P.C.Pinto,P.Thiran,and M.Vetterli,Locating the source of diffusion in large-scale networks,Phys.Rev.Lett.,109:068702,2012.
[28]D.Shah and T.Zaman,Rumors in a network:Who’s the culprit?,IEEE Trans.Inf.Theory,57(8):5163–5181,2011.
[29]W.Luo,W.P.Tay,and M.Leng,Identifying infection sources and regions in large networks,IEEE Trans.Signal Process.,61(11):2850–2865,2013.
[30]W.Dong,W.Zhang,and C.W.Tan,Rooting out the rumor culprit from suspects,Information Theory Proceedings(ISIT),2013 IEEE International Symposium on Information Theory,2013.
[31]K.Zhu and L.Ying,Information source detection in the SIR model:a sample path based approach,in Information Theory and Applications Workshop,2013.
[32]W.Luo and W.P.Tay,Finding an infection source under the SIS model,Acoustics,Speech and Signal Processing(ICASSP),2013 IEEE International Conference on Acoustics,Speech and Signal Processing,2013.
[33]Y.Zhang,Z.Wang,and C.Xia,Identifying key users for targeted marketing by mining online social network,in Proc.24th IEEE International Conference on Advanced Information Networking and Applications Workshops,2010.
[34]M.Gomez Rodriguez,J.Leskovec,and A.Krause,Inferring networks of diffusion and influence,in Proc.16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2010.
[35]E.Bakshy,J.M.Hofman,W.A.Mason,and D.J.Watts,Everyone’s an influencer:quantifying influence on Twitter,in Proc.4th ACM International Conference on Web Search and Data Mining,2011.
[36]A.-L.Barabasi,R.Albert,H.Jeong,Mean-fi eld theory for scale-free random networks,Physica A,272(1-2):173-187,1999;
[37]A.-L.Barabasi,R.Albert,H.Jeong,Scale-free characteristics of random networks:the topology of the worldwide web,Physica A,281(1-4):69–77,2000.
[38]P.L.Krapivsky,S.Redner,F.Leyvraz,Connectivity of growing random networks,Phys.Rev.Lett.,85:4629,2000;
[39]Z.Liu,Y.-C.Lai,N.Ye,Statistical properties and attack tolerance of growing networks with algebraic preferential attachment,Phys.Rev.E,66:036112,2002.