Network Structural Analysis via Core-Tree-Decomposition
published: Oct. 7, 2014, recorded: August 2014, views: 1975
Report a problem or upload filesIf you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
The study of network analysis is still a new science; currently, the structure of real-world networks is described only in terms of the coarsest and basic details such as diameter and degree distribution. To efficiently and effectively implement network analysis techniques, a more comprehensive grasp of their finer mathematical structure is required. The seminal work by Leskovec et al. tackled this issue by decomposing networks into two parts; namely "whiskers" and "cores."
In this study, we progress toward this issue by obtaining a novel "core-tree-decomposition," which is a variant of the well-known tree-decomposition. Specifically, we perform experiments to construct core-tree-decompositions for as many as 40 publicly available datasets. Our decomposition provides more structural information than the previous method in the following ways:
1. By comparing the eigenvalue distribution of the cores obtained by our decomposition method with that of the Erdos-Renyi random graphs, we confirm that, unlike the previously defined core, our "core" behaves like a random graph, i.e., an expander graph. Thus, the intuition that the cores should be "expander-like" is confirmed by the eigenvalue distribution of our cores.
2. By deleting the core, we obtain a tree-decomposition of small width, which behaves like a tree. Therefore, we can say that whiskers are "tree-like," and can be explained in terms of "tree-width."
3. We show that the cores of real networks widely range in size, which implies that their tree-widths are also quite varied. Furthermore, we show theoretical and empirical evidence that tree-width plays a significant role in the efficiency of certain types of algorithms.
Download slides: kdd2014_maehara_network_structural_analysis_01.pdf (490.7 KB)
Link this pageWould you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !