Browsing by Author "Yu, Pei-Duo"

Now showing 1 - 4 of 4

Averting Cascading Failures in Networked Infrastructures: Poset-Constrained Graph Algorithms
(2018-08-01)
Yu, Pei-Duo
;
Tan, Chee Wei
;
Fu, Hung-Lin
;
交大名義發表
;
應用數學系
Cascading failures in critical networked infrastructures that result even from a single source of failure often lead to rapidly widespread outages as witnessed in the 2013 Northeast blackout in Northern America. The ensuing problem of containing future cascading failures by placement of protection or monitoring nodes in the network is complicated by the uncertainty of the failure source and the missing observation of how the cascading might unravel, be it the past cascading failures or the future ones. This paper examines the problem of minimizing the outage when a cascading failure from a single source occurs. A stochastic optimization problem is formulated where a limited number of protection nodes, when placed strategically in the network to mitigate systemic risk, can minimize the expected spread of cascading failure. We propose the vaccine centrality, which is a network centrality based on the partially ordered sets (poset) characteristics of the stochastic program and distributed message-passing, to design efficient approximation algorithms with provable approximation ratio guarantees. In particular, we illustrate how the vaccine centrality and the poset-constrained graph algorithms can be designed to tradeoff between complexity and optimality, as illustrated through a series of numerical experiments. This paper points toward a general framework of network centrality as statistical inference to design rigorous graph analytics for statistical problems in networks.
Optimal Detection of Influential Spreaders in Online Social Networks
(2016)
Tan, Chee Wei
;
Yu, Pei-Duo
;
Lai, Chun-Kiu
;
Zhang, Wenyi
;
Fu, Hung-Lin
The wide availability of digital data in online social networks such as the Facebook offers an interesting question on finding the influential users based on the user interaction over time. An example is the clicking of the Facebook "Like" button to endorse a digital object (e.g., a post or picture) posted by other user. This online interaction activity connects users sharing similar opinions or disposition and spreads their influence. In this paper, we study the estimation problem of finding a small number of users in the online social network who are influential in maximizing the reach of a digital message when it originates from them. The digital interaction in the online social network can be modeled using an interaction graph, e.g., associate users through the past record of snapshot observations of Like\'s activity in Facebook. We propose a network centrality approach in which we first use graph convexity to characterize the relative influential level of users on the interaction graph. We then propose a message passing algorithm to rank these users in order to identify the influential spreaders who play a forward-engineering role in catalyzing the spread of a new message. A useful application is to schedule a cascade of endorsement of a digital marketing message or for a business entity with a Facebook presence to find a number of Facebook users to spread the word of new commercial products. Lastly, we describe the performance of our algorithm using a synthetic dataset.
Rumor source detection for rumor spreading on random increasing trees
(2015-01-06)
Fuchs, Michael
;
Yu, Pei-Duo
;
應用數學系
;
Department of Applied Mathematics
In a recent paper, Shah and Zaman proposed the rumor center as an effective rumor source estimator for rumor spreading on random graphs. They proved for a very general random tree model that the detection probability remains positive as the number of nodes to which the rumor has spread tends to infinity. Moreover, they derived explicit asymptotic formulas for the detection probability of random d - regular trees and random geometric trees. In this paper, we derive asymptotic formulas for the detection probability of grown simple families of random increasing trees. These families of random trees contain important random tree models as special cases, e. g., binary search trees, recursive trees and plane- oriented recursive trees. Our results show that the detection probability varies from 0 to 1 across these families. Moreover, a brief discussion of the rumor center for unordered trees is given as well.
Rumor Source Detection in Unicyclic Graphs
(2017-01-01)
Yu, Pei-Duo
;
Tan, Chee Wei
;
Fu, Hung-Lin
;
交大名義發表
;
National Chiao Tung University
Detecting information source in viral spreading has important applications such as to root out the culprit of a rumor spreading in online social networks. In particular, given a snapshot observation of the network topology of nodes having the rumor, how to accurately identify the initial source of the spreading? In the seminal work [Shah et el. 2011], this problem was formulated as a maximum likelihood estimation problem and solved using a rumor centrality approach for graphs that are degree-regular trees. The case of graphs with cycles is an open problem. In this paper, we address the maximum likelihood estimation problem by a generalized rumor centrality for spreading in unicyclic graphs. In particular, we derive a generalized rumor centrality that leads to a new graph-theoretic design approach to inference algorithms.