Markov Tensor Theory and Cascade, Reachability, and Routing in Complex Networks
2017-12
Loading...
View/Download File
Persistent link to this item
Statistics
View StatisticsJournal Title
Journal ISSN
Volume Title
Title
Markov Tensor Theory and Cascade, Reachability, and Routing in Complex Networks
Authors
Published Date
2017-12
Publisher
Type
Thesis or Dissertation
Abstract
In this dissertation, we study and characterize the networks as the medium and substrate for communications, interactions, and flows by addressing various crucial problems under the general topics of cascade, reachability, and routing. These are general problem domains common in several applications and from a variety of networks. We address these problems in a unified way by a theoretical platform that we have developed in this research, which we call Markov Tensor Theory. How does a phenomena, influence, or a failure cascade in a network and what are the key factors in this cascade? We study the influence cascade in social networks and introduce the Heat Conduction (HC) Model which captures both social influence and non-social influence, and extends many of the existing non-progressive models. We then prove that selecting the optimal seed set of influential nodes for maximizing the influence spread is NP-hard for HC, however, by establishing the submodularity of influence spread, we tackle the influence maximization problem with a scalable and provably near-optimal greedy algorithm. We also study failure cascade in inter-dependent networks where we considered the effects of cascading failures both within and across different layers. In this study, we investigate how different couplings (i.e., inter-dependencies) between network elements across layers affect the cascading failure dynamics. How failures or disruptions affect the network in terms of reachability of entities from each other, how to identify the reachabilities efficiently after failures, and who are the pivotal players in the reachabilities? We develop an oracle to answer dynamic reachabilities efficiently for failure-prone networks with frequent reachability query requirement. Founded on the concept of reachability, we also introduce and provide a formulation for finding articulation points, measuring network load balancing, and computing pivotality ranking of nodes. Once the reachabilities are determined, how to quickly and robustly route a flow from a part of the network to the other part of a network under the failures? To avoid solely relying on the shortest path and generate alternative paths on one hand, and to correct the degeneracy of hitting time distance, on the other hand, we develop a novel routing continuum method from shortest-path routing to all-path routing which provides both a closed form formulation for computing the continuum distances and an efficient routing strategy. We also devise an oracle for efficiently answering to single-source shortest path queries as well as finding the replacement paths in the case of multiple failures. For these studies, we develop Markov Tensor Theory as a platform of powerful theories and tools founded on Markov chain theory and random walk methods which supports the general weighted and directed networks.
Keywords
Description
University of Minnesota Ph.D. dissertation. 2017. Major: Electrical Engineering. Advisor: Zhi-Li Zhang. 1 computer file (PDF); 180 pages.
Related to
Replaces
License
Collections
Series/Report Number
Funding information
Isbn identifier
Doi identifier
Previously Published Citation
Suggested citation
Golnari, Golshan. (2017). Markov Tensor Theory and Cascade, Reachability, and Routing in Complex Networks. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/194608.
Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.