Generating Graphs with Predefined k-Core Structure

author: Marco Gaertler, Faculty of Informatics, University of Karlsruhe
published: Dec. 14, 2007,   recorded: October 2007,   views: 3817


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.


The modeling of realistic networks is of great importance for complex systemsresearch. Previous procedures typically model the natural growth of networks byiteratively adding nodes, use geometric positioning information, define linkconnectivity with preference for nearest neighbors or already highly connectednodes, or combine several of these approaches. Our novel model is based on the well-know concept of 'k'-cores, originally introduced in social network analysis. Recent studies exposed the significant 'k'-core structure of several real world systems, e.g. the AS network of theInternet. We present two algorithms for generating networks which strictlyadhere to the sizes of a given 'k'-core structure but also exhibit adaptationto various use cases. We showcase this in a comparative evaluation with twowell-known AS network generators.

See Also:

Download slides icon Download slides: eccs07_gaertler_ggp_01.v1.pdf (4.3┬áMB)

Help icon Streaming Video Help

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: