Link to the University of Pittsburgh Homepage
Link to the University Library System Homepage Link to the Contact Us Form

Critical Elements Detection in Dynamic Networks Under Uncertainty

Gillen, Colin P. (2019) Critical Elements Detection in Dynamic Networks Under Uncertainty. Doctoral Dissertation, University of Pittsburgh. (Unpublished)

[img] PDF (Copyright permission letter from Wiley Periodicals)
Supplemental Material
Restricted to University of Pittsburgh users only until 11 September 2024.

Download (112kB) | Request a Copy
[img] PDF (Copyright permission from Springer)
Supplemental Material
Restricted to University of Pittsburgh users only until 11 September 2024.

Download (86kB) | Request a Copy
[img] PDF (updated v3 with changes)
Primary Text
Restricted to University of Pittsburgh users only until 11 September 2024.

Download (2MB) | Request a Copy


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.


Social Networking:
Share |


Item Type: University of Pittsburgh ETD
Status: Unpublished
CreatorsEmailPitt UsernameORCID
Gillen, Colin P.cpg12@pitt.educpg12
ETD Committee:
TitleMemberEmail AddressPitt UsernameORCID
Committee ChairProkopyev, Oleg A.droleg@pitt.edudroleg
Committee MemberRajgopal, Jayantrajgopal@pitt.edurajgopal
Committee MemberMatsypura,
Committee MemberGomez, Andresagomez@pitt.eduagomez
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 2019 14:32


Monthly Views for the past 3 years

Plum Analytics

Actions (login required)

View Item View Item