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 comm unity detection. For a given network G\, each partition of the vertices has a \;modularity score\, with higher values indicating that the pa rtition 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 &le\; q*(G) &le\; 1. \;

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

\n\nGuimera et al 2004 showed that the E rdö\;s-Ré\;nyi random graph Gn\,p with n vertices and edge-pro bability p can have surprisingly high modularity and \;that this sho uld be taken into account when determining statistical significance of c ommunity structures in networks. Further\, they predicted Gn\,p \;to have modularity order (np)-1/3. \; \;

\n\nOur two key fin dings are that the modularity is 1 + o(1) with high probability (whp) fo r 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 co mpeting prediction by Reichardt and Bornholdt in 2006 based on spin glas s \;methods. \; \;

\n\n2. Sampling sufficiency for det ermining modularity. \;

\n\nWe analyse when community structur e 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 str ucture of the underlying network.

\n\nJoint work with Colin McDiar mid and based on the paper '\;Modularity of Erdö\;s-Ré\;nyi random graphs'\; [arxiv.org/abs/1808.02243]. \;

\n\n\ ;

\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 e xactly once. Suppose we take a random subgraph G(p) of G by keeping any edge independently with probability p. The resiliency of Dirac'\;s th eorem 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.

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