Seminarier AI

  • Datum: –14.00
  • Plats: Ångströmlaboratoriet 4004
  • Arrangör: Matematiska institutionen
  • Kontaktperson: Erik Ekström
  • Seminarium

10:15 Xing Shi Cai

Two applications of random directed graphs in computer science

Abstract: Various random undirected graphs models have been intensively studied in recent years as models for complex networks. However, random directed graphs have attracted far less attentions. In this talk I will introduce two examples where random directed graphs are used to study problems in computer science.

The first example is the random k-out graph. It can be used as models for studying Deterministic Finite Automaton (DFA), which plays a fundamental role in language theories and have applications in pattern matching and lexical analysis. The second example is the Kademlia network, which is widely used in peer-to-peer networks on the Internet such as BitTorrent and Ethereum.


11:15 Fiona Skerman

Community structure in Networks - limits of learning.

Modularity is at the heart of the most popular algorithms for community detection. For a given network G, each partition of the vertices has a modularity score, with higher values indicating that the partition better captures community structure in G. The (max) modularity q*(G) of the network G is defined to be the maximum over all vertex partitions of the modularity score, and satisfies 0 ≤ q*(G) ≤ 1. 

1. "When is there Modularity from fluctuations in Random Graphs?"

Guimera et al 2004 showed that the Erdös-Rényi random graph Gn,p with n vertices and edge-probability p can have surprisingly high modularity and that this should be taken into account when determining statistical significance of community structures in networks. Further, they predicted Gn,p to have modularity order (np)-1/3.  

Our two key findings are that the modularity is 1 + o(1) with high probability (whp) for np up to 1 + o(1) and no further; and when np ≥ 1 and p is bounded below 1, it has order (np)−1/2 whp, in accord with a competing prediction by Reichardt and Bornholdt in 2006 based on spin glass methods.  

2. Sampling sufficiency for determining modularity. 

We analyse when community structure of an underlying network can be determined from its observed network. In a natural model where we suppose edges in an underlying graph G appear with some probability in our observed graph G' we describe how high a sampling probability we need to infer the community structure of the underlying network.

Joint work with Colin McDiarmid and based on the paper 'Modularity of Erdös-Rényi random graphs' []. 

13:15 Tony Johansson

The resiliency of Dirac's Hamilton cycle theorem

Abstract: Dirac's theorem states that if a graph G on n vertices has minimum degree at least n/2, then G contains a Hamilton cycle, i.e. a cycle passing through each vertex exactly once. Suppose we take a random subgraph G(p) of G by keeping any edge independently with probability p. The resiliency of Dirac's theorem is the smallest p for which G(p) still contains a Hamilton cycle. I will show that as long as p is such that G(p) has minimum degree two, then it has a Hamilton cycle with high probability.