Graph connectivity and vector degree in motif-based graphs

degree;graph theory;data mining

Wang, Qihao ; Chang ; Kevin Chen-Chuan

关键词: degree;    graph theory;    data mining;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/107975/WANG-THESIS-2020.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

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.