Master of Sciences (Engineering), Case Western Reserve University, 2024, EECS - Computer and Information Sciences

In the field of link prediction, determining an accurate understanding of how well algorithms are performing is important to make informed decisions about how the algorithms can best be utilized. Existing metrics are reliant on using a setting's known links to judge the algorithm's accuracy, typically using a train-test split. However, if assessing link prediction in a setting for which the ground truth is difficult to determine or subject to sample bias, this can lead to errors that are not easily detected by standard link prediction validation. As a solution to this, we propose using model-based validation (MBV) as an alternative assessment for link prediction algorithms, where the algorithm is graded based on how well it reflects a model underlying the data. Additionally, we test a type of network refinement to see if degree bias as a mechanism for sample bias can be addressed by changing the network's degree distribution directly.

Committee: Mehmet Koyutürk (Advisor); Sanmukh Kuppannagari (Committee Member); Kevin Xu (Committee Member) Subjects: Computer Science

Doctor of Philosophy, Case Western Reserve University, 2023, EECS - Computer and Information Sciences

This dissertation presents a comprehensive approach to advancing proteomics and under-studied proteins in network biology, emphasizing the development of reliable algorithms, fair evaluation practices, and accessible computational tools. A key contribution of this work is the introduction of RoKAI, a novel algorithm that integrates multiple sources of functional information to infer kinase activity. By capturing coordinated changes in signaling pathways, RoKAI significantly improves kinase activity inference, facilitating the identification of dysregulated kinases in diseases. This enables deeper insights into cellular signaling networks, supporting targeted therapy development and expanding our understanding of disease mechanisms. To ensure fairness in algorithm evaluation, this research carefully examines potential biases arising from the under-representation of under-studied proteins and proposes strategies to mitigate these biases, promoting a more comprehensive evaluation and encouraging the discovery of novel findings. Additionally, this dissertation focuses on enhancing accessibility by developing user-friendly computational tools. The RoKAI web application provides a convenient and intuitive interface to perform RoKAI analysis. Moreover, RokaiXplorer web tool simplifies proteomic and phospho-proteomic data analysis for researchers without specialized expertise. It enables tasks such as normalization, statistical testing, pathway enrichment, provides interactive visualizations, while also offering researchers the ability to deploy their own data browsers, promoting the sharing of findings and fostering collaborations. Overall, this interdisciplinary research contributes to proteomics and network biology by providing robust algorithms, fair evaluation practices, and accessible tools. It lays the foundation for further advancements in the field, bringing us closer to uncovering new biomarkers and potential therapeutic targets in diseases like cancer, Alzheimer' (open full item for complete abstract)

Committee: Mehmet Koyutürk (Committee Chair); Mark Chance (Committee Member); Vincenzo Liberatore (Committee Member); Kevin Xu (Committee Member); Michael Lewicki (Committee Member) Subjects: Bioinformatics; Biomedical Research; Computer Science

Master of Sciences, Case Western Reserve University, 0, EECS - Computer and Information Sciences

Link prediction is a constantly growing field, but the evaluation of newly developed algorithms requires a lot of computational resources that can be prohibitively expensive to perform on large networks. To resolve this issue, a possible approach is to reduce the computational complexity by randomly sampling the negative edges. Here, we investigate the effect of negative sampling on the evaluation of link prediction algorithms, propose models to estimate the sampling error based on the number of negative edges sampled, and suggest minimum values bounding the error to a desired amount. Across a wide-array of real networks, we show that the suggested values can appropriately bound the error and can speed up the evaluation process ~1000x times for large networks having $10^6$ nodes with minimal error. We anticipate that these results and our estimated model can help researchers keep the evaluation of link prediction methods accessible on large, real-world networks.

Committee: Mehmet Koyuturk (Advisor); Michael Lewicki (Committee Chair); Soumya Ray (Committee Member) Subjects: Computer Science

Master of Science, University of Toledo, 2022, Engineering (Computer Science)

Data from various disciplines, such as complex social, biological, and physical systems are naturally represented by networks. The stochastic block model (SBM) is one of the most widely used generative models for network data. Many continuous-time dynamic network models are built upon the same assumption as the SBM: edges or events between all pairs of nodes are conditionally independent given the block or community memberships. In this thesis, we propose two models: First, we introduce the multivariate community Hawkes (MULCH) model, an extremely flexible community-based model for continuous-time networks. Contrary to the SBM assumption which prevents them from reproducing higher-order motifs such as triangles that are commonly observed in real networks, MULCH introduces dependence between node pairs using structured multivariate Hawkes processes. We fit the model using a spectral clustering and likelihood-based local refinement procedure. We find that our proposed MULCH model is far more accurate than existing models both for predictive and generative tasks. Next, we propose the marked block Hawkes model (marked BHM), designed to model dynamic networks characterized by both timestamps and marks. The marked BHM replaces the univariate Hawkes process in the original BHM model with a marked Hawkes process to model such networks. We show that modeling both timestamps and marks improves community detection and predictive accuracy.

Committee: Kevin Xu (Committee Chair); Ahmed Javaid (Committee Member); Gursel Serpen (Committee Member) Subjects: Computer Science; Statistics

Master of Science in Engineering, University of Toledo, 2021, Engineering (Computer Science)

The advancement in data collection has resulted in unprecedented quantity and variety of network data with diverse applications. This thesis analyzes two such network settings. The first is a computed transplant compatibility network which has a bipartite representation. We conduct local network analysis on this network and attempt link prediction on missing compatibilities. We conclude that while the techniques we develop result in modest prediction accuracy, we are able to provide an overview of the network and demonstrate the absence of some network properties we may otherwise expect. The second analysis performed is conducted on social network data, one of the most common targets for network analysis. Data compiled from these networks are perfect for analyzing social trends. One such trend that this thesis aims to address is political homophily. Evidence of political homophily is well researched and indicates that people have a strong tendency to interact with others with similar political ideologies. Additionally, as links naturally form in a social network either through recommendations or indirect interaction, new links are very likely to reinforce communities. This serves to make social media more insulated and ultimately more polarizing. We aim to address this problem by providing link recommendations that will reduce network homophily. We propose several variants of common neighbor-based link prediction algorithms that aim to recommend links to users who are similar but also would decrease homophily. We demonstrate that acceptance of these recommendations can indeed reduce the homophily of the network, whereas acceptance of link recommendations from a standard Common Neighbors algorithm does not.

Committee: Kevin Xu (Advisor); Qin Shao (Committee Member); Gursel Serpen (Committee Member) Subjects: Computer Science; Mathematics

Master of Science (MS), Wright State University, 2021, Computer Science

Link prediction in the domain of scientific collaborative networks refers to exploring and determining whether a connection between two entities in an academic network may emerge in the future. This study aims to analyze the relevance of academic collaborations and identify the factors that drive co-author relationships in a heterogeneous bibliographic network. Using topological, semantic, and graph representation learning techniques, we measure the authors' similarities w.r.t their structural and publication data to identify the reasons that promote co-authorships. Experimental results show that the proposed approach successfully infer the co-author links by identifying authors with similar research interests. Such a system can be used to recommend potential collaborations among the authors.

Committee: Tanvi Banerjee Ph.D. (Advisor); Krishnaprasad Thirunarayan Ph.D. (Committee Member); Michael L. Raymer Ph.D. (Committee Member) Subjects: Artificial Intelligence; Computer Science

Master of Science (MS), Wright State University, 2021, Computer Science

Scientific collaboration between researchers is very common and much influential and ground-breaking research is performed by teams comprised of scientist from different fields and organizations. In this thesis, we analyze and model a small scientific collaboration network limited to two organizations: Wright State University and the Air Force Research Laboratory. Research paper co-authorship is used for establishing the network structure. We analyze several network properties and compare them to past results from analysis of larger and more diverse collaboration networks. We show that the two-organization network we explored exhibits properties similar to those of larger networks. Guided by advances in state-of-the-art algorithms for the link prediction problem in large-scale networks, we explore modeling of the local network via similar methods. We use a variety of link prediction algorithms and models, from simple to state-of-the-art, and compare their accuracy. Results of our experiments suggest that simple and easy to calculate prediction methods produce robust results, outperforming the more complicated state-of-the-art models we explored. We observe a variety of methods producing very accurate predictions, which suggests these methods can be effectively used to solve practical real-world problems associated with small local or intra-organizational networks.

Committee: Michael L. Raymer Ph.D. (Advisor); Mateen M. Rizki Ph.D. (Committee Member); Travis E. Doom Ph.D. (Committee Member); Thomas Wischgoll Ph.D. (Committee Member) Subjects: Computer Science

Master of Science, University of Toledo, 2020, Engineering (Computer Science)

In many application settings involving networks, such as friendships or messages among users of an on-line social network and transactions between traders in financial markets, understanding network dynamics has been a long-standing problem with implications in numerous disciplines including computer science, physics, mathematics, biology, social sciences, and economics. Due to high computational complexity of dynamic network analysis, most models assume networks are static which sacrifices expressiveness for scalability. Here we set forth two new concepts which enhance link prediction and recommendation as well as modeling communities and interactions in continuous-time dynamic networks. In particular, we first introduce the notion of personalized degree and find that neighbors with higher personalized degree are more likely to lead to new link formations when they serve as common neighbors with other nodes, both in undirected and directed settings. Next, we propose the Community Hawkes Independent Pairs (CHIP) generative model for continuous-time networks of timestamped relational events. We show that spectral clustering provides consistent community detection, for a growing number of nodes, on networks generated by the CHIP model and develop consistent and computationally efficient estimators for the model parameters. Personalized degree provides a lens into the latent information in the topology of on-line social networks and how this information can be utilized to better understand the evolution of a network over time and to predict future interactions. We find that incorporating personalized degree into common neighbor based link prediction algorithms can improve mean link prediction accuracy by up to 35%, while incorporating directions of edges further improves accuracy by up to 11%. Moreover, the CHIP model is able to capture network dynamics and its underlying community structure with only a few parameters and scale to much larger networks compared t (open full item for complete abstract)

Committee: Kevin Xu (Committee Chair); Ahmad Y Javaid (Committee Member); Qin Shao (Committee Member) Subjects: Computer Science

PhD, University of Cincinnati, 2020, Engineering and Applied Science: Computer Science and Engineering

Graphs arise naturally in many complex systems where they are used to represent entities and relationships between them. The analysis of graph-based models has wide applications like evaluating the significance of interactions between individual entities, identifying important subcomponents, discovering hidden interactions, and making complex inferences about the functions of the underlying systems. Many of these applications require meaningful representation of nodes, and several graph-embedding algorithms have recently been developed to embed nodes in meaningful vector spaces. However, it is not clear how the performance of these algorithms depends on the structural features of graphs, which can vary a lot across real world domains. It would thus be useful to identify the main features that influence the performance of embedding approaches, and to develop a method that can determine the most suitable method for any given graph. The research described in this dissertation applies a systematic approach to comparing various graph-embedding methods on several types of graphs, relates their performance to the structural features of the graphs, and develops a system to select the best embedding method based on graph features. By evaluating the node embedding algorithms for link prediction on several synthetic graph models and real-world network datasets, this study demonstrates the fact that the structural properties of a graph have a significant effect on how well any given node embedding algorithm performs on it. For a particular graph, the performance of a node embedding algorithm can be predicted based on the structural properties, and this relationship holds across a wide range of network types and real-world networks. The results in this dissertation lead to several insights about which algorithms work for various types of graphs.

Committee: Ali Minai Ph.D. (Committee Chair); Raj Bhatnagar Ph.D. (Committee Member); Yizong Cheng Ph.D. (Committee Member); Jaroslaw Meller Ph.D. (Committee Member); Carla Purdy Ph.D. (Committee Member) Subjects: Computer Science

Master of Sciences, Case Western Reserve University, 2020, EECS - Computer and Information Sciences

Link prediction in network analysis is generally defined as the prediction of edges that will emerge in an evolving network. Recent studies have shown that features which take into account the global topology of the network, based random walks, can be effective. Unfortunately, inherent noise in the network adversely affects the accuracy of global topology based solutions, and the size of networks creates challenges for the feasibility of solutions in terms of run-time. Here, we propose a novel approach that utilizes a set of specially selected nodes –which we call anchor nodes- to construct low-dimensional topological profiles for the nodes in network. Our algorithm then uses these profiles to make predictions. This dimensionality reduction makes our predictions more robust to noise. It also allows us to divide our algorithm into pre-computation and live query phases, greatly improving our runtime performance. We investigate various criteria for choosing anchor nodes including page-rank centrality and node degree, and develop methods to diversify the set of anchor nodes. Our experimental results on social network datasets show that anchor set based link prediction significantly outperforms other state-of-the-art approaches.

Committee: Mehmet Koyuturk (Committee Chair); Erman Ayday (Committee Member); Yinghui Wu (Committee Member) Subjects: Computer Science

Doctor of Philosophy, University of Toledo, 2018, Engineering

Many application settings involve the analysis of timestamped relations or events between a set of entities, e.g. messages between users of an on-line social network. Dynamic network models are typically used as analysis tools in these settings. They work by either aggregating events over time to form network snapshots, or model the network directly in continuous time. In dynamic network models the common problem researchers deal with is link prediction, which has been studied extensively in the literature, and many methods have been proposed. However On-line social networks (OSNs) often contain different types of relationships between users. When studying the structure of OSNs such as Facebook, two of the most commonly studied networks are friendship and interaction networks. The link prediction problem in friendship networks has been heavily researched. In Interaction networks where links are both added and removed over time, the link prediction or forecasting problem is more complex and involves predicting both newly added and newly removed links. This problem setting creates new challenges in the evaluation of dynamic link prediction methods. In this dissertation, I investigate several metrics currently used for evaluating the accuracy of dynamic link prediction methods and demonstrate why they are inappropriate and misleading in many cases. I provide several recommendations and propose a new metric to characterize link prediction accuracy fairly and effectively using a single number. The link prediction problem in interaction networks is still ongoing and in this Dissertation, I study the predictive power of combining friendship and interaction networks. By leveraging friendship networks, I show that I can improve the accuracy of link prediction in interaction networks. I observe that leveraging friendships improves the accuracy of predicting interactions between people that have never interacted before, but has little or no impact on interactions between (open full item for complete abstract)

Committee: Kevin Xu (Committee Chair); Vijay Devabhaktuni (Committee Co-Chair); Tian Chen (Committee Member); Ahmad Javaid (Committee Member); Scott Pappada (Committee Member) Subjects: Computer Science; Mathematics; Sociology; Statistics

Doctor of Philosophy, Case Western Reserve University, 2017, EECS - Computer Engineering

Link prediction is at the heart of a large class of network analytics and information retrieval techniques, including recommendation systems, threat detection, and disease gene prioritization, among others. A commonly utilized feature in link prediction is network proximity, which is assessed using a variety of algorithms, ranging from effective resistance to random walks. Network proximity is useful in link prediction, since it has been repeatedly shown in many contexts that nodes that have many shared connections or are proximate to each other are likely to interact with each other in the future. Many network proximity measures are based on algebraic formulations and their computations utilize iterative methods. Owing to their importance, significant effort has been devoted to accelerating the iterative processes that underlie network proximity computations. These techniques rely on numerical properties of power iterations, as well as structural properties of the networks to reduce the runtime of iterative algorithms. However, the acceleration provided by existing techniques is usually not sufficient to enable real-time processing of proximity queries on networks with millions of nodes and tens of millions of edges. In this thesis, we present several algebraic approaches to the acceleration of network proximity queries, with a view to facilitating real-time query processing on very large networks. We first develop an algorithm to speed up the iterative computation of random walk based proximity, using Chebyshev polynomials for undirected networks. We show that our approach, called Chopper, yields provable improvements in convergence rate, and significantly reduced convergence times in practice. We then focus on the same problem for directed networks, and develop an indexing scheme that exploits the sparsity of real-life networks. We show that our algorithm, I-Chopper, significantly outperforms existing methods and it offers both scalability and efficiency (open full item for complete abstract)

Committee: Mehmet Koyuturk (Advisor) Subjects: Computer Science

MS, University of Cincinnati, 2016, Engineering and Applied Science: Computer Science

With the increase in number of social networks and technological advancements in the last two decades, there is vast amount of digital communication happening between people. Most of these communication networks evolve with time and can be represented in the form of graphs. Link Prediction is finding edges that may appear in the future in the network using the current data in the network. Link prediction finds many applications such as “Recommender systems” in social networks like Facebook, Twitter, LinkedIn etc. Link prediction is a vast area and many link prediction algorithms exist today each catering to its specific purpose. Some of these algorithms deal with the problem of link prediction in Time-evolving graphs and they have comparatively better performance than a random predictor. However, their raw performance, when considered by itself, can still be improved. In our work, we aim to develop an algorithm that not only has comparatively better performance than the random predictor, but also to have very good raw performance. In this work, the main idea for link prediction is to take into account the past data along with the current data to predict the edges to be formed in the future. To do this, we calculate the conditional probability of two nodes having an edge between them in the future given they have certain feature value. Proximity measures are taken as features between the nodes, and they are calculated for every possible edge. Bayesian inference is used to calculate the posterior probability of an edge to occur in the future, given we have current and past data. Past data is used to calculate Prior probability of edges. We also experimented with the way Prior probability of an edge is computed by changing the way in which it is computed currently, and observed the algorithm's behavior with this version of Prior probability. Using this methodology, our algorithm is tested against different types of datasets and the relevancy measures such as (open full item for complete abstract)

Committee: Raj Bhatnagar Ph.D. (Committee Chair); Nan Niu Ph.D. (Committee Member); Yizong Cheng Ph.D. (Committee Member) Subjects: Computer Science

PhD, University of Cincinnati, 2015, Engineering and Applied Science: Computer Science and Engineering

It can be said, without exaggeration, that social networks have taken a large segment of population by a storm. Regardless of the actual geographical location, of socio-economic status, as long as access to an internet connected computer is available, a person has access to the whole world, and to a multitude of social networks. By being able to share, comment, and post on various social networks sites, a user of social networks becomes a "citizen of the world", ensuring presence across boundaries (be they geographic, or socio-economic boundaries). At the same time social networks have brought forward many issues interesting from computing point of view. One of these issue is that of evaluating similarity between nodes/profiles in a social network. Such evaluation is not only interesting, but important, as the similarity underlies the formation of communities (in real life or on the web), of acquisition of friends (in real life and on the web). In this thesis, several methods for finding similarity, including semantic similarity, are investigated, and a new approach, Wordnet-Cosine similarity is proposed. The Wordnet-Cosine similarity (and associated distance measure) combines both a lexical database, Wordnet, with Cosine similarity (from information retrieval) to find possible similar profiles in a network. In order to assess the performance of Wordnet-Cosine similarity measure, two experiments have been conducted. The first experiment illustrates the use for Wordnet-Cosine similarity in community formation. Communities are considered to be clusters of profiles. The results of using Wordnet-Cosine are compared with those using four other similarity measures (also described in this thesis). In the second set of experiments, Wordnet-Cosine was applied to the problem of link prediction. Its performance of predicting links in a random social graph was compared with a random link predictor and was found to achieve better accuracy.

Committee: Anca Ralescu Ph.D. (Committee Chair); Irene Diaz Ph.D. (Committee Member); Rehab M. Duwairi Ph.D. (Committee Member); Kenneth Berman Ph.D. (Committee Member); Chia Han Ph.D. (Committee Member); Dan Ralescu Ph.D. (Committee Member) Subjects: Computer Science

PhD, University of Cincinnati, 2012, Engineering and Applied Science: Computer Science and Engineering

One of the most challenging problems in the post-genomic era for computer scientists and bioinformaticians is to identify meaningful patterns from a huge amount of data describing a variety of molecular systems. Networks provide a unifying representation for these various molecular systems, such as protein interaction maps, transcriptional regulations, metabolites and reactions, signaling transduction pathways, and functional associations. On one hand, computational determination of molecular networks is of interest due to the tremendous labor and cost associated with large-scale wet-lab experiments. On the other hand, novel methods and approaches are in need to extract useful and meaningful patterns from established large-scale molecular networks. In this thesis, we tackle the problems of computationally predicting links to construct large-scale protein interaction maps, transcriptional regulatory networks, and disease related heterogeneous networks. In particular, we adopted a supervised learning framework for link prediction in protein interaction maps of a human pathogen, and performed network analysis to extract and identify novel drug targets for disease treatment. We developed and demonstrated a semi-supervised learning approach for link prediction in a transcriptional regulatory network, and further analyzed the biological relevance of identified links. In the thesis, we also developed and performed computational approaches to extract biologically meaningful patterns in large-scale protein interaction maps and disease- and gene-related networks. Similar to other real-life systems, molecular networks are dynamic and context-dependent. We comparatively analyzed the static conglomerate networks and context-dependent networks and systematically revealed their differences in global topological characteristics, subnetwork structure components, and functional compartments. Finally, we applied network analysis to extract interesting patterns in networks of rare hu (open full item for complete abstract)

Committee: Raj Bhatnagar PhD (Committee Chair); Long Lu PhD (Committee Chair); Anil Jegga DVM MRes (Committee Member); Yan Xu PhD (Committee Member); Yizong Cheng PhD (Committee Member); John Schlipf PhD (Committee Member) Subjects: Computer Science

Doctor of Philosophy, The Ohio State University, 2008, Computer and Information Science

This work seeks to develop a probabilistic framework for modeling, querying and analyzing large-scale structured and semi-structured data. The framework has three components: (1) Mining non-redundant local patterns from data; (2) Gluing these local patterns together by employing probabilistic models (e.g., Markov random field (MRF), Bayesian network); and (3) Reasoning over the data for solving various data analysis tasks. Our contributions are as follows: (a) We present an approach of employing probabilistic models to identify non-redundant itemset patterns from a large collection of frequent itemsets on transactional data. Our approach can effectively eliminate redundancies from a large collection of itemset patterns. (b) We propose a technique of employing local probabilistic models to glue non-redundant itemset patterns together in tackling the link prediction task in co-authorship network analysis. Our technique effectively combines topology analysis on network structure data and frequency analysis on network event log data. The main idea is to consider the co-occurrence probability of two end nodes associated with a candidate link. We propose a method of building MRFs over local data regions to compute this co-occurrence probability. Experimental results demonstrate that the co-occurrence probability inferred from the local probabilistic models is very useful for link prediction. (c) We explore employing global models, models over large data regions, to glue non-redundant itemset patterns together. We investigate learning approximate global MRFs on large transactional data and propose a divide-and-conquer style modeling approach. Empirical study shows that the models are effective in modeling the data and approximately answering queries on the data. (d) We propose a technique of identifying non-redundant tree patterns from a large collection of structural tree patterns on semi-structured XML data. Our approach can effectively eliminate redundancies from a larg (open full item for complete abstract)

Committee: Srinivasan Parthasarathy (Advisor) Subjects: Computer Science