Graph connectivity and vector degree in motif-based graphs

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.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Electrical & Computer Engr

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2020

Author dc:creator

• Wang, Qihao

Contributors dc:contributor

• Chang, Kevin Chen-Chuan

• data mining
• degree
• graph theory

Statement dc:rights

• Copyright 2020 Qihao Wang

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/107975

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/107975