Correctly Modeling Networks

author: Tamara Kolda, Sandia National Laboratories
published: Oct. 12, 2016,   recorded: August 2016,   views: 981

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.


Understanding and modeling go hand in hand – we develop models not only to make predictions but also to see where the models fail and there is more to do. Large-scale networks are immensely challenging to model mathematically. In this talk, we present our arguments for what features are important to measure and reproduce. In the undirected case, we show that graphs with high clustering coefficients (i.e., many triangles) must have dense Erdȍs-Rényi subgraphs. This is a key theoretical finding that may yield clues in understanding network structure. Following this line, we propose the Block Two-level Erdȍs-Rényi (BTER) model because it reproduces a given degree distribution and clustering coefficient profile (i.e., the triangle distribution), scales linearly in the number of edges, and is easily parallelized. We also consider the extension of this work to bipartite graphs, where we consider bipartite four-cycles, and propose a bipartite BTER (biBTER) model. These models can be used to generate artificial graphs that capture salient features of real graphs. We compare the artificial and real-world graphs so that we can understand where the models are accurate or not. Time permitting, we also explain how these models can be specified with very few parameters, which is useful for benchmarking purposes. We close with open questions for future investigations. This is joint work with S. Aksoy, A. Pinar, T. Plantenga, and C. Seshadhri.

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: