10:15 Xing Shi Cai

\n\nTwo applications of random dir ected graphs in computer science

\n\nAbstract: Various random undi rected graphs models have been intensively studied in recent years as mo dels for complex networks. However\, random directed graphs have attract ed far less attentions. In this talk I will introduce two examples where random directed graphs are used to study problems in computer science.< /p>\n\n

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 netwo rk\, which is widely used in peer-to-peer networks on the Internet such as BitTorrent and Ethereum.

\n\n\;

\n\n11:15 Fiona Sker man

\n\nCommunity structure in Networks - limits of learning.

\ n\nModularity is at the heart of the most popular algorithms for community detection. For a given network G\, eac h partition of the vertices has a \;modularity score\, with higher values indicating that the partition b etter captures community structure in G. The (max) modularity q*(G) of t he \;network G is defined to be t he maximum over all vertex partitions of the modularity score\, and sati sfies 0 &le\; q*(G) &le\; 1. \;

\n\n1. "\;When is there Modularity from fluctuations in Random Graphs?"\;

\n\nGuimera et al 2004 showed that the Erd&o uml\;s-Ré\;nyi random graph Gn\,p with n vertices and edge-probabi lity p can have surprisingly high modularity and \;that this should be taken into account when determining stati stical significance of community structures in networks. Further\, they predicted Gn\,p \;to have modular ity order (np)-1/3. \; \;

\n\nOur two key findings are that the modularity is 1 + o(1) with hig h probability (whp) for np up to 1 + o(1) and no further\; and when np & ge\; 1 and p \;is bounded below 1 \, it has order (np)&minus\;1/2 whp\, in accord with a competing predict ion by Reichardt and Bornholdt in 2006 based on spin glass \; methods. \; \;

\n\nWe analyse when community structure of an un derlying network can be determined from its observed network. In a natur al model where we suppose \;edges in an underlying graph G appear with some probability in our observed graph G& #39\; we describe how high a sampling probability we need to infer \ ;the community structure of the under lying network.

\n\nJoint work w ith Colin McDiarmid and based on the paper '\;Modularity of Erdö\ ;s-Ré\;nyi random graphs'\; [arxiv.org/abs/1808.02243]. \;< /span>

\n\n13:15 Tony Johansson

\n\nThe resiliency of Dirac'\;s Hamilton cycle theorem

\n\nAbstract: 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 r andom subgraph G(p) of G by keeping any edge independently with probabil ity p. The resiliency of Dirac'\;s theorem is the smallest p for whic h 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 wi th high probability.

\n DESCRIPTION: SUMMARY:Seminarier AI LOCATION:Ångströmlaboratoriet\, 4004 TZID:Europe/Stockholm DTSTART:20190611T101500 DTEND:20190611T140000 UID:20190611T101500-45670@uu.se END:VEVENT END:VCALENDAR