Locating the Sources of Contagion Processes in Networks
Add to Google Calendar
Date: Wed, April 15, 2015
Time: 4:30-5:30 PM
Location: Holmes Hall 389
Speaker: Lei Ying, Associate Professor, School of Electrical, Computer and Energy Engineering, Arizona State University
Abstract:
This talk focuses on the problem of identifying the contagion source in networks. Contagion processes can be used to model many real-world phenomena, including rumor spreading in online social networks, epidemics in human beings, and malware on the Internet. Informally speaking, locating the source of a contagion process refers to the problem of identifying a node in the network that provides the best explanation of the observed contagion. In this talk, I will introduce a sample path based approach for locating contagion sources. The approach is to identify the most likely sample path and then view the source of the optimal sample path as the source. In the first part of the talk, I will show that on infinite tree networks, the sample path based estimator is a node that minimizes the maximum distance to the infected nodes. Furthermore, the estimator is within a constant distance from the actual source with a high probability, independent of the size of the infection sub-network. In the second part of the talk, I will present a ranking-on-graphs approach for locating the source when partial timestamps of the contagion process are available. I will present two ranking algorithms developed based on the sample path based approach. Both of them perform well in experimental evaluations using synthetic data and real-world social network data.
Biography:
Professor Lei Ying received his B.E. degree from Tsinghua University, Beijing, China, and his M.S. and Ph.D in Electrical and Computer Engineering from the University of Illinois at Urbana-Champaign. He currently is an Associate Professor at the School of Electrical, Computer and Energy Engineering at Arizona State University, and an Associate Editor of the IEEE/ACM Transactions on Networking.
His research interest is broadly in the area of stochastic networks, including social networks, cloud computing, and communication networks. He is coauthor with R. Srikant of the book Communication Networks: An Optimization, Control and Stochastic Networks Perspective, Cambridge University Press, 2014.
He won the Young Investigator Award from the Defense Threat Reduction Agency (DTRA) in 2009 and NSF CAREER Award in 2010. He was the Northrop Grumman Assistant Professor in the Department of Electrical and Computer Engineering at Iowa State University from 2010 to 2012. He received the best paper award at IEEE INFOCOM 2015.
Date: Wed, April 15, 2015
Time: 4:30-5:30 PM
Location: Holmes Hall 389
Speaker: Lei Ying, Associate Professor, School of Electrical, Computer and Energy Engineering, Arizona State University
Abstract:
This talk focuses on the problem of identifying the contagion source in networks. Contagion processes can be used to model many real-world phenomena, including rumor spreading in online social networks, epidemics in human beings, and malware on the Internet. Informally speaking, locating the source of a contagion process refers to the problem of identifying a node in the network that provides the best explanation of the observed contagion. In this talk, I will introduce a sample path based approach for locating contagion sources. The approach is to identify the most likely sample path and then view the source of the optimal sample path as the source. In the first part of the talk, I will show that on infinite tree networks, the sample path based estimator is a node that minimizes the maximum distance to the infected nodes. Furthermore, the estimator is within a constant distance from the actual source with a high probability, independent of the size of the infection sub-network. In the second part of the talk, I will present a ranking-on-graphs approach for locating the source when partial timestamps of the contagion process are available. I will present two ranking algorithms developed based on the sample path based approach. Both of them perform well in experimental evaluations using synthetic data and real-world social network data.
Biography:
Professor Lei Ying received his B.E. degree from Tsinghua University, Beijing, China, and his M.S. and Ph.D in Electrical and Computer Engineering from the University of Illinois at Urbana-Champaign. He currently is an Associate Professor at the School of Electrical, Computer and Energy Engineering at Arizona State University, and an Associate Editor of the IEEE/ACM Transactions on Networking.
His research interest is broadly in the area of stochastic networks, including social networks, cloud computing, and communication networks. He is coauthor with R. Srikant of the book Communication Networks: An Optimization, Control and Stochastic Networks Perspective, Cambridge University Press, 2014.
He won the Young Investigator Award from the Defense Threat Reduction Agency (DTRA) in 2009 and NSF CAREER Award in 2010. He was the Northrop Grumman Assistant Professor in the Department of Electrical and Computer Engineering at Iowa State University from 2010 to 2012. He received the best paper award at IEEE INFOCOM 2015.