Analysis of the Structural Properties and Formation of Complex Networks
2018-08
Loading...
View/Download File
Persistent link to this item
Statistics
View StatisticsJournal Title
Journal ISSN
Volume Title
Title
Analysis of the Structural Properties and Formation of Complex Networks
Authors
Published Date
2018-08
Publisher
Type
Thesis or Dissertation
Abstract
Many real-world systems around us can be described as complex networks (e.g., electric grids, cyber-physical systems, chemical and energy systems). Hence, there has been a quickly growing interest in such networks, since they can help us to represent, analyze and evaluate many of the complex and dynamic systems that have become a critical resource in our daily and social life (i.e., the Internet and the World Wide Web, online social networks and road networks). Complex networks have been studied in different contexts (i.e., communities extraction, path lengths, cluster coefficient and degree distributions, small-world networks, etc.) for a long time. However, the possible organizing principles shaping the observed topology of complex networks are still not well understood. In this dissertation, we advance the current knowledge in understanding the topology and formation of complex systems. More specifically, we explore the concept of “reciprocal network” and present new methods to “uncover” and “dissect” the core structure of complex networks with the goal of improving our understanding of such systems. First, we present a comprehensive measurement-based characterization of the reciprocal network extracted from a directed complex network – using the online social network Google+ as a case study – and its evolution over time, with the goal to gain insights into the structural properties of a complex network. In a sense, the reciprocal network can be viewed as the stable skeleton network of a directed network that holds it together. Thus, it could reveal the possible organizing principles shaping the observed network topology of a directed complex network. Second, we have advanced and developed an effective procedure to extract the core structure of complex networks. To achieve this, we propose two new metrics a node “dependence value” and a subgraph “nucleon-index”. Then, using these metrics, we proposed a modified version of the traditional k-shell decomposition method by identifying the $k_C$-index where we should stop pruning the network in order to preserve its core structure and extract a meaningful “core” for complex networks. Third, with the goal of dissecting the structure of the nucleus of a massive complex network, we propose a two-step procedure to hierarchically unfold the nucleus of complex networks by building up and generalizing ideas from the existing clique percolation approaches. Our scheme builds (hyper)graphs that provide us with a “big picture” view of the core structure of a complex network and how it is formed. Our methodology is very scalable and can be applied to massive complex networks (hundreds million nodes and billion edges). In summary, this thesis proposes new tools to understand the structural properties and formation of complex networks. Our developed schemes are capable of: i) helping to understand possible organizing principles shaping the observed network topology of a directed complex network; ii) extracting the core structure of complex networks; and iii) dissecting the structure of the dense nucleus of massive complex networks.
Description
University of Minnesota Ph.D. dissertation. 2018. Major: Computer Science. Advisor: Zhi-Li Zhang. 1 computer file (PDF); 117 pages.
Related to
Replaces
License
Collections
Series/Report Number
Funding information
Isbn identifier
Doi identifier
Previously Published Citation
Suggested citation
Dumba, Braulio. (2018). Analysis of the Structural Properties and Formation of Complex Networks. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/201053.
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.