Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


27909.pdf (7.64 MB)

ETD Abstract Container

Abstract Header

Analysis of Meso-scale Structures in Weighted Graphs

Sardana, Divya
http://rave.ohiolink.edu/etdc/view?acc_num=ucin1510927111275038

Abstract Details

2017, PhD, University of Cincinnati, Engineering and Applied Science: Computer Science and Engineering.
Many real world systems across multiple disciplines, like social, biological and information networks can be described as complex networks, i.e., assemblies of nodes and edges having nontrivial topological properties. Along with network topology, most real world networks provide useful connectivity strength information between nodes in the form of edge weights. For example, in a co-authorship network, edge weights could represent the number of publications shared by two authors. This information of edge weights can be leveraged along with the network topological properties to uncover many hidden and interesting properties inherent in these networks. Meso-scale structures can help in analysing network properties which are not very evident at either the global level (eg. network diameter) or at the local level (eg. node degree). In this dissertation, we develop novel methodologies for the analysis of weighted networks or graphs at the meso-scale. Specifically, we develop algorithms to find two types of meso-scale structures in graphs, namely, community structure and core periphery structure. The first problem that we solve involves finding density-based, disjoint clusters or communities in a weighted graph. We develop a novel graph clustering algorithm called G-MKNN based upon a node affinity measure called Mutual K-nearest neighbors. Our algorithm is based upon a new definition of density called SE-density which tries to achieve a balance between structural density and edge-weight homogeneity in the final clustering. We compare our algorithm with other state-of-the-art weighted and un-weighted graph clustering algorithms using both synthetic and real world protein-protein interaction (PPI) datasets. The second problem that we solve involves extracting core periphery structures in weighted graphs. In this work, first, we formalize the definition of core periphery structures for weighted networks. Next, we build two algorithms to extract core-periphery structures in a weighted graphs. We also develop a methodology to categorize and score the peripheries surrounding a core. Using synthetic and real world datasets, we demonstrate the importance of studying core-periphery structures in weighted graphs. We further provide a case study using a dataset of crimes taking place in San Francisco to demonstrate the usefulness of core periphery structures found by the developed algorithms in studying temporal and spatial networks. An inherent drawback in most clustering algorithms is that they do not find any overlap among the clusters, which can be a source of crucial information in many areas. Moreover, overlapping communities are naturally present in many domains such as social networks. In the third problem, we extend our graph clustering algorithm developed in problem one to find overlapping clusters (OG-MKNN). We use both a synthetic dataset as well as a real world weighted social network to illustrate the effectiveness of our algorithm. The fourth problem that we solve involves developing a semi-supervised clustering algorithm (SG-MKNN) with the help of biological domain knowledge to find clusters in protein-protein interaction networks. We embed gene ontology based functional information into an MKNN based clustering algorithm for making better informed clustering decisions. We demonstrate the effectiveness of the algorithms developed using real world PPI datasets.
Raj Bhatnagar, PhD (Committee Chair)
Yizong Cheng, PhD (Committee Member)
Anil Jeggal, PhD (Committee Member)
Ali Minali, PhD (Committee Member)
Tomas Stepinski, PhD (Committee Member)
176 p.
Computer Science
community structure; core periphery structure; graph clustering; protein protein interaction networks; semi supervised clustering; overlapping clustering

Recommended Citations

Citations

  • Sardana, D. (2017). Analysis of Meso-scale Structures in Weighted Graphs [Doctoral dissertation, University of Cincinnati]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1510927111275038

    APA Style (7th edition)

  • Sardana, Divya. Analysis of Meso-scale Structures in Weighted Graphs. 2017. University of Cincinnati, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=ucin1510927111275038.

    MLA Style (8th edition)

  • Sardana, Divya. "Analysis of Meso-scale Structures in Weighted Graphs." Doctoral dissertation, University of Cincinnati, 2017. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1510927111275038

    Chicago Manual of Style (17th edition)

ucin1510927111275038
680
© 2017, all rights reserved.
This open access ETD is published by University of Cincinnati and OhioLINK.