Gillen, Colin P.
(2019)
Critical Elements Detection in Dynamic Networks Under Uncertainty.
Doctoral Dissertation, University of Pittsburgh.
(Unpublished)
Abstract
Network cascades represent a number of real-life applications: social influence, wildfires, electrical grid failures, viral spread, and so on. The commonality between these phenomena is that they begin from a set of seed nodes and dynamically spread throughout the network via some time-dependent mechanism. We study this class of problem through the lens of critical elements detection; that is, identifying important nodes/arcs responsible for propagation. Specifically, given a set of seed nodes and the Linear Threshold (LT) model, our initial work determines which arcs (e.g., relationships in a social network) are most critical to influence propagation. We prove NP-hardness of the problem. Time-dependent/time-independent mixed-integer programming (MIP) models are introduced. We develop an MIP-based exact algorithm - rooted in the idea of (information) diffusion expansion - and propose a new centrality measure.
Real-life data typically involve uncertainty; thus, we extend the scope of the above work via the robust critical node fortification problem. Here, the decision-maker fortifies nodes (within a budget) against cascades under uncertain conditions. In particular, the arc weights - how much influence one node has on another - are uncertain but are known to lie in some range. This problem is shown to be NP-hard. We formulate an MIP and improve its continuous relaxation via nonlinearity/convexification. We specify an MIP-based Expand-and-cut exact solution algorithm - the expansion enhanced by cutting planes, themselves tied to the expansion process. These results motivate two novel (inter-related) centrality measures.
One particular application of our work involves wildfire fuel treatment. Wildfires are a natu- rally occurring phenomenon, and, while they perform important ecological functions, the proximity of human activities to forest landscapes requires control/preparedness to mitigate damage. One technique utilized by forest managers is fuel management, where a portion of available combustible material is removed through fuel treatment, such as prescribed burning. We formulate a discrete network optimization model to decide the timing/location of fuel treatments; these decisions es- sentially involve identifying critical nodes in a dynamic cascade network. Our model accounts for fuel levels/growth, prevailing wind direction/strength, fuel moisture, and sustainability considera- tions. A case study is conducted on a particular region of northeastern Texas, a landscape prone to wildfires.
Share
| Citation/Export: |
|
| Social Networking: |
|
Details
| Item Type: |
University of Pittsburgh ETD
|
| Status: |
Unpublished |
| Creators/Authors: |
|
| ETD Committee: |
|
| Date: |
11 September 2019 |
| Date Type: |
Publication |
| Defense Date: |
20 June 2019 |
| Approval Date: |
11 September 2019 |
| Submission Date: |
1 July 2019 |
| Access Restriction: |
5 year -- Restrict access to University of Pittsburgh for a period of 5 years. |
| Number of Pages: |
150 |
| Institution: |
University of Pittsburgh |
| Schools and Programs: |
Swanson School of Engineering > Industrial Engineering |
| Degree: |
PhD - Doctor of Philosophy |
| Thesis Type: |
Doctoral Dissertation |
| Refereed: |
Yes |
| Uncontrolled Keywords: |
Critical Elements Detection
Dynamic Networks
Mixed-Integer Programming
Robust Optimization
Wildfire Fuel Management |
| Date Deposited: |
11 Sep 2019 14:32 |
| Last Modified: |
11 Sep 2024 05:15 |
| URI: |
http://d-scholarship.pitt.edu/id/eprint/37023 |
Metrics
Monthly Views for the past 3 years
Plum Analytics
Actions (login required)
 |
View Item |
![[feed]](/images/feed-icon-32x32.png){kind=icon}