Graduation Semester and Year
Summer 2025
Language
English
Document Type
Thesis
Degree Name
Master of Science in Computer Science
Department
Computer Science and Engineering
First Advisor
Sharma Chakravarthy
Abstract
Applications need to be modeled for analyses. With the availability of many alternate data Models, choosing one needs to be done carefully by considering the complexity of data to be modeled and its analyses requirements. Social networks and other newer applications are primarily relationship-oriented and also have multiple types of entities and relationships. Although simple and attributed graphs have been used historically for modeling these applications, recently, multilayer networks (or MLNs) have been shown to be more effective in preserving the semantics of the application better and further provide flexibility of analyses. However, choice of MLN as a data model poses additional challenges for analyses as extant simple and attributed graph algorithms cannot be used directly.
A wide range of computations can be performed on graphs, including traversals, searches, path-finding, to name a few. Our interest in this thesis is in aggregate analyses on MLNs, such as community, centrality, substructure etc. For these, new algorithms are being developed for MLNs to leverage modeling advantages.
Briefly, MLNs consist of multiple graphs or layers (also called networks), each capturing a different type of relationship or interaction. MLNs can be categorized into: Homogeneous MLNs (HoMLNs), where each layer represents a relationship in the form of intra-layer edges and all layers have the same type of entity; Heterogeneous MLNs (HeMLNs), where layers represents a different relationship based on entity type in that layer, and inter-layer edges representing relationships between entity types from two layers; and Hybrid MLNs (or HyMLNs), which combine both homogeneous and heterogeneous characteristics. While many algorithms exist for analyzing simple graphs, weighted or unweighted, to the best of our knowledge, these algorithms are not available for MLNs and are being developed only recently.
Algorithms for MLNs can be developed in multiple ways. Recently, a decoupling framework has been proposed and its advantages have been demonstrated. This framework separates the analyses into two stages: independent analysis of each layer and composing results from each layer for MLN analysis. Each layer of the HoMLN is analyzed independently using any layer-specific analysis function, without using the knowledge of other layers. The partial results from two layers are then composed to derive the overall results for the HoMLN. This approach is not only efficient, thanks to the potential for parallelism during the analysis stage, but has also been shown to be efficient and scalable.
For validating MLN algorithms, typically, layers are aggregated using Boolean AND or OR operations (suited for unweighted graphs) and existing algorithms are used. This has been shown to lead to ambiguity in edge interpretation, not preserving layer characteristics, and information loss in general. The goal of MLN algorithms is to preserve accuracy avoiding information loss. Weighted graphs pose additional issues for aggregation as, in addition to Boolean operations, weights can be combined in multiple ways, such as sum, max, min, or average. Challenges for developing decoupling-based MLN algorithms for weighted MLNs are: i) choice of aggregation method, ii) composition algorithm, iii) tradeoff on information carried over from layer analysis and used for composition, and iv) intuition-based heuristics for maximizing accuracy.
This thesis focuses on generalizing decoupling-based algorithms for weighted MLNs, specifically HoMLNs and for degree centrality metric. Although algorithms have been developed for unweighted MLNs, to the best of our knowledge, these have not been done for weighted MLNs. As the decoupling-based algorithms use independently generated analysis information from layers, accuracy is a primary challenge. To address this, the thesis proposes a set of heuristics for degree centrality that aim to maximize accuracy and efficiency while carrying over minimal metric information from layers. These heuristics are compared against both ground truth and naive baseline to evaluate their effectiveness. Proposed heuristics demonstrate comparable accuracy to the ground truth while significantly reducing computation time and outperforming the naive approach in both performance and precision.
To validate the proposed algorithms, synthetically generated HoMLN data sets of different sizes, distribution, overlap, and weight characteristics are used. In addition, real-world datasets have been utilized to establish that the heuristics developed work on real-world data sets equally well. This ensures that the heuristics are tested across graphs with diverse structures and characteristics. Jaccard similarity for accuracy and execution time are used for performance. Scalability of the algorithms is established using numerous increasingly large data sets.
Keywords
Multilayer network analysis, Degree centrality, Weighted multilayer network
Disciplines
Computer Sciences
License
This work is licensed under a Creative Commons Attribution-NonCommercial-Share Alike 4.0 International License.
Recommended Citation
Ayowole-Obi, Ayomide, "Centrality Algorithms For Weighted Homogeneous Multilayer Networks" (2025). Computer Science and Engineering Theses. 531.
https://mavmatrix.uta.edu/cse_theses/531