Network Structural Analysis via Core-Tree-Decomposition

author: Takanori Maehara, National Institute of Informatics
published: Oct. 7, 2014,   recorded: August 2014,   views: 1975
Categories

Slides

Related Open Educational Resources

Related content

Report a problem or upload files

If 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.
Lecture popularity: You need to login to cast your vote.
  Bibliography

Description

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.

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Write your own review or comment:

make sure you have javascript enabled or clear this field: