Browsing by Author "Tan, Chee Wei"

Now showing 1 - 5 of 5

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.
Graph Algorithms for Preventing Cascading Failures in Networks
(2018-01-01)
Yu, Pei Duo
;
Tan, Chee Wei
;
Fu, Hung-Lin
;
交大名義發表
;
National Chiao Tung University
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. This paper examines the problem of minimizing the outage when a cascading failure from a single source occurs. An optimization problem is formulated where a limited number of protection nodes, when placed strategically in the network to mitigate systemic risk, can minimize the spread of cascading failure. Computationally fast distributed message-passing algorithms are developed to solve this problem. Global convergence and the optimality of the algorithm are proved using graph theoretic analysis. In particular, we illustrate how the poset-constrained graph algorithms can be designed to address the trade-off between complexity and optimality.
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 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.
Wireless Max-Min Utility Fairness With General Monotonic Constraints by Perron-Frobenius Theory
(2016-12)
Zheng, Liang
;
Hong, Y. -W. Peter
;
Tan, Chee Wei
;
Hsieh, Cheng-Lin
;
Lee, Chia-Han
This paper presents a systematic approach for solving wireless max-min utility fairness optimization problems in multiuser wireless networks with general monotonic constraints. These problems are often challenging to solve due to their non-convexity. By establishing a connection between this class of optimization problems and the class of conditional eigenvalue problems that can be addressed by a generalized nonlinear Perron-Frobenius theory, we show how these problems can be solved optimally using an iterative algorithm that converges geometrically fast. The mathematical development in this paper unifies previous work and allows us to handle a broader class of competitive utility functions with general nonlinear monotonic constraints. Several representative applications illustrate the effectiveness of the proposed framework, including the max-min quality-of-service subject to robust interference temperature constraints in cognitive radio networks, the min-max weighted mean-square error subject to signal-to-interference-and-noise ratio constraints in multiuser downlink systems, the max-min throughput subject to nonlinear power constraints in energy-efficient wireless networks, the max-min sigmoid utility in multimedia wireless networks, and the min-max outage probability subject to outage constraints in heterogeneous wireless networks. Numerical results are presented to demonstrate the fast-convergence behavior of the algorithms to the optimal fixed-point solution characterized by our generalized nonlinear Perron-Frobenius theoretic framework.