PC Seminar: "Distances in random trees" and "Sampling and community structure in bipartite graphs "

10:15 - 11:00: Ekaterina Toropova

Title: Sampling and community structure in bipartite graphs

Abstract: Consider a sampled graph Gp, which is derived from a bipartite graph G by preserving each edge with probability p. To assess how clearly the community structure is present in a graph and which vertex partition captures it best, it is common to use modularity. We provide sufficient conditions for the edge sampling probability p such that the bipartite modularity of the sampled graph is likely to be a good approximation of the bipartite modularity of the underlying graph.

11:00 - 11:15: Break/Fika

11:15 - 12:00: Jacob Lundblad

Title: Distances in random trees

Abstract: The Wiener index of a graph G is defined as the sum of the distances between all pairs of vertices in G. In this master thesis we introduce recursive trees, plane oriented recursive trees (PORTs) and simply generated trees. We then present results by Neininger [1], Munsonius and R ̈uschendorf [2] and Janson [3] for the expectation and limiting distribution of the Wiener index of these families. For recursive trees and PORTs the results follow from analysing the recursive structure of the trees and the contraction method, while the results for simply generated trees is based on a limiting object, the continuum random tree.

[1] R. Neininger, The Wiener index of random trees, Combin. Probab. Comput. 11 (6) (2002) 587–597.

[2] G.O.Munsonius, L.Ruschendorf, Limit theorems for depths and distances in weighted random b-ary recursive trees, Journal of Applied Probability 48 (4) (2011) 1060–1080.

[3] S. Janson, The Wiener index of simply generated random trees, Random Structures Algorithms 22 (4) (2003) 337–358

This is a seminar in our seminar series on Probability and Combinatorics (PC).