# European Institute for Statistics, Probability, Stochastic Operations Research and their Applications

About | Research | Events | Reports | Alumni | ContactHome

September 19-22, 2017

Workshop
on

Community Detection

and

Network Reconstruction

 SUMMARY REGISTRATION SPEAKERS PROGRAMME ABSTRACTS

SUMMARY

Recent advances in the study of networks in the physics, mathematics and computer science communities have provided novel probabilistic tools to address various network-related problems of practical relevance. Two seemingly different, but actually intimately related, problems are community detection and network reconstruction.
Community detection is the identification of groups of nodes that share some property (e.g., are densely connected with each other in a given real-world network). This seemingly simple task presents us with several computational and analytical challenges, even in very simple and idealized scenarios.
Network reconstruction problems, on the other hand, attempt to infer features of a real-world network, of which only partial and/or aggregate information is available (e.g., inference from a sample of a subset of the network).
These two broad classes of problems are conveniently tackled using random graph models that preserve some observed features of the real network, while providing a probabilistic estimate for the unobserved features.
This workshops focuses on various aspects of community detection and network reconstruction. Emphasis will be put on the interdisciplinary nature of both problems, and contributions will highlight both the applied and the theoretical side.

## ORGANIZERS

 Luca Avena Leiden University Jop Briët CWI Rui Castro TU Eindhoven Diego Garlaschelli Leiden University

CONFIRMED SPEAKERS

 Sebastien Bubeck Ton Coolen King's College London Jean-Charles Delvenne Gao Fengnan Andrea Gabrielle Iman van Lelyveld De Nederlandsche Bank Po-Ling Loh Laurent Massoulie Raj Rao Nadakuditi Tiago P. Peixoto Federico Ricci-Tersenghi Tiziano Squartini Vincent Traag Nicolas Tremblay Nicolas Verzelen Ernst Wit

PROGRAMME

MONDAY September 18

TUESDAY September 19

WEDNESDAY September 20

THURSDAY September 21

FRIDAY September 22

***************************************************************************************************************************************

ABSTRACTS

Sebastien Bubeck

New results in distributed optimization and consensus learning

Consider a graph where each vertex v is associated to a convex function f_v. Assume that each vertex is a computing unit with oracle access to its associated function. We consider the distributed optimization problem of reaching the minimum of f:=\sum_v f_v. We show how the expansion properties of the graph and the conditioning of f interact in the description of the fundamental limits for this problem. A practical decentralized algorithm will also be presented with experiments for least-squares and logistic regression. (The talk assumes no prior knowledge in convex optimization.)
(joint work with Francis Bach, Yin Tat Lee, Laurent Massoulie and Kevin Scaman)

Ton Coolen

Tailored random graph ensembles: analysis, generation algorithms, and loops

In many disciplines one would like to tailor' (or deform) random graphs, i.e. build statistical features into their topologies, so that they can be used as more realistic models of observed real-world networks. This can be achieved in a systematic and unbiased manner using
hard- or soft-constrained maximum entropy ensembles, in which the values of appropriate domain-specific observables are imposed as constraints.
Such ensembles provide a rich source of problems for the theorist. For various interesting examples it is possible to compute analytically the leading orders in the system size of the Shannon entropy (using statistical mechanical tools and path integrals), and also to derive useful macroscopic information-theoretic graph dissimilarity measures and eigenvalue spectra. Moreover, generating samples from graph ensembles with hard constraints via MCMC, to serve e.g. as null models'
in hypothesis tests or as proxies for real networks in simulations of processes, turns out to be somewhat tricky. Often the hard constraints require elementary moves in the MC process whose execution can create unwanted sampling biases. In addition, these ensembles often exhibit complex phase transitions, which makes the correct sampling of states even more difficult. Finally, I will turn to ensembles in which the imposed constraints create nontrivial numbers of short loops, so that most of our analytical tools (which tend to be based on, and benefit from, locally tree-like topology) can no longer be used. I will discuss new analytical approaches to `loopy' graph ensembles, and results from simple toy models.

Fengnan Gao

Statistical Estimation of Preferential Attachment Networks

The preferential attachment (PA) network is a popular way of modeling the social networks, the collaboration networks and etc. The PA network model is an evolving network where new nodes keep coming in. When a new node arrives, it establishes only one connection with an existing node. The random choice on the existing node is via a multinomial distribution with probability weights based on a preferential function $f$ on the degrees. $f$ is assumed apriori non-decreasing, which means the nodes with high degrees are more likely to get new connections, i.e., "the rich get richer". We proposed an estimator on $f$, that maps the natural numbers to the positive real line. We show, with techniques from branching process, our estimator is consistent. If $f$ is affine, meaning $f(k) = k + \delta$, it is well known that such a model leads to a power-law degree distribution. We proposed a maximum likelihood estimator for $\delta$ and establish the asymptotic normality and efficiency on the MLE. If the PA function is sublinear and assumes a parametric form, then we show the maximum likelihood estimator is also efficient, despite the difficulty in analyzing the likelihood. We will also talk about some recent advances revealing the connection between the empirical estimator and the maximum likelihood estimator.
(joint work with Aad van der Vaart)

Po-Ling Loh

Optimal rates for community estimation in the weighted stochastic block model

Community identification in a network is an important problem in fields such as social science, neuroscience, and genetics. Over the past decade, stochastic block models (SBMs) have emerged as a popular statistical framework for this problem. However, SBMs have an important limitation in that they are suited only for networks with unweighted edges; in various scientific applications, disregarding the edge weights may result in a loss of valuable information. We study a weighted generalization of the SBM, in which observations are collected in the form of a weighted adjacency matrix and the weight of each edge is generated independently from an unknown probability density determined by the community membership of its endpoints. We characterize the optimal rate of misclustering error of the weighted SBM in terms of the Renyi divergence of order 1/2 between the weight distributions of within-community and between-community edges, substantially generalizing existing results for unweighted SBMs. Furthermore, we present a principled, computationally tractable algorithm based on discretization that achieves the optimal error rate without assuming knowledge of the weight densities.

PRACTICAL INFORMATION

### ●      Venue

Eurandom, Mathematics and Computer Science Dept, TU Eindhoven,

Den Dolech 2, 5612 AZ  EINDHOVEN,  The Netherlands

Eurandom is located on the campus of Eindhoven University of Technology, in the (4th floor) (about the building). The university is located at 10 minutes walking distance from Eindhoven main railway station (take the exit north side and walk towards the tall building on the right with the sign TU/e).
Accessibility TU/e campus and map.

### ●      Registration

Registration is free, but compulsory for speakers and participants. Registration is now open. Please go to: REGISTRATION

### ●      Accommodation

For invited speakers and organizers we will take care of accommodation. Other attendees will have to make their own arrangements.

For hotels around the university, please see: Hotels (please note: prices listed are "best available").  Reimbursement available up to 80 euro per night.

More hotel options can be found on the webpages of the , Postbus 7, 5600 AA Eindhoven.

### ●      Travel

For those arriving by plane, there is a convenient direct train connection between Amsterdam Schiphol airport and Eindhoven. This trip will take about one and a half hour. For more detailed information, please consult the NS travel information pages.

Many low cost carriers also fly to Eindhoven Airport. There is a bus connection to the Eindhoven central railway station from the airport. (Bus route number 401) For details on departure times consult http://www.9292ov.nl

The University  can be reached easily by car from the highways leading to Eindhoven (for details, see our route descriptions or consult our map with highway connections.

### ●      Conference facilities : Conference room, Metaforum Building  MF11&12

The meeting-room is equipped with a data projector, an overhead projector, a projection screen and a blackboard. Please note that speakers and participants making an oral presentation are kindly requested to bring their own laptop or their presentation on a memory stick.

### ●      Conference Secretariat

Upon arrival, participants should register with the workshop officer, and collect their name badges. The workshop officer will be present for the duration of the conference, taking care of the administrative aspects and the day-to-day running of the conference: registration, issuing certificates and receipts, etc.

### ●      Contact

Mrs. Patty Koorn, Workshop Officer, Eurandom/TU Eindhoven, koorn"at"eurandom.tue.nl

#### Last updated 17-07-17, by PK

P.O. Box 513, 5600 MB Eindhoven, The Netherlands
tel. +31 40 2478100
e-mail: info@eurandom.tue.nl