Files in this item

FilesDescriptionFormat

application/pdf

application/pdfWANG-THESIS-2020.pdf (289kB)
(no description provided)PDF

Description

Title:Graph connectivity and vector degree in motif-based graphs
Author(s):Wang, Qihao
Advisor(s):Chang, Kevin Chen-Chuan
Department / Program:Electrical & Computer Eng
Discipline:Electrical & Computer Engr
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:M.S.
Genre:Thesis
Subject(s):degree
graph theory
data mining
Abstract:Graph theory is frequently used to model and encode relationships in social networks, the internet, or biology. Due to the fundamental limitation that an edge can only connect two nodes, a standard graph is only capable of describing pairwise relationships. Therefore, some new models have been introduced to capture the relationships among more than two nodes by replacing standard edges with novel representations, like motif-edge or hyperedge. By replacing standard edges with motif-edges, the graph succeeds in describing the higher-order complex networks. However, a problem of connectivity in motif-based graphs also arises because generated motif-based graphs can be disconnected even though the standard graphs are connected. Here we first survey existing works on connectivity metrics in standard graphs, then propose a new measurement of degree, called vector degree, to extend the definition of degree from standard graphs to motif-based graphs. Some properties of vector degree will be compared with standard degree, and some connectivity metrics will be extended to motif-based graphs as well.
Issue Date:2020-05-10
Type:Thesis
URI:http://hdl.handle.net/2142/107975
Rights Information:Copyright 2020 Qihao Wang
Date Available in IDEALS:2020-08-26
Date Deposited:2020-05


This item appears in the following Collection(s)

Item Statistics