Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
  
 

Research Seminar (Winter Term 2019)

<previous seminar | next seminar>

Description

A series of talks on current research and interesting topics in algorithm engineering and theoretical computer science. Everyone is welcome to attend talks. 

If you want to give a talk about a topic in algorithm engineering or theoretical computer science, please write an e-mail to Prof. Tobias Friedrich or to Ralf Rothenberger.

Announcements

For announcements of talks, subscribe to our mailing list.

Talks (click on title to show abstract)

Date Room Speaker Title
30.10. 15:00 G-1 E.15/16 Fabian Sommer

Hyperbolic random graphs have become a popular random graph model over the last decade, as they resemble many real-world graphs. In particular, they have a heterogeneous degree distribution, high clustering and a small-world property. Another property of graphs that distinguishes technical and biological from social networks is degree assortativity – a measure that describes the correlation between degrees of adjacent nodes. Most technical and biological graphs are found to have a significant negative assortativity, while the assortativity of social networks is usually positive. However, hyperbolic random graphs offer no way to control the degree assortativity.

We explore and compare multiple ways to extend hyperbolic random graphs or the similar geometric inhomogeneous random graphs so that the expected assortativity can be controlled while maintaining the properties that made hyperbolic random graphs attractive in the first place. In particular, we describe a model with controllable assortativity that has high clustering, small-world and a heterogeneous degree distribution. We also describe how such graphs can be generated efficiently.