
Seminars /
20112012 July 2, 2012, 14:30Special seminar (special day and time) Gupta and Kumar showed that in a network of $n$ stationary nodes, network capacity scales as order of \sqrt{\frac{n}{\log n}} and packet delivery delay is almost negligible as packets are relayed like 'hot potatoes'. June 28, 2012, 15:15Special seminar (special day and time) This talk will discuss distributed algorithms for separable convex optimization
by multiple cooperating agents. Specifically, we will describe a class of algorithms,
recently proposed in the literature, for approximating the minimum of a separable convex
function. These algorithms are fully distributed, require no centralized supervision, and
are robust to unpredictable link and node failures. This makes them particularly useful in
distributed control applications, such as formation control and coverage control. June 21, 2012, 11:00This seminar will be on Thursday Rationality of consumers supports the most important results in Economic
Theory. Traditionally, this feature is understood as an ability to
maximize a personal utility function. However, from Optimization Theory we
know that the optimization problems are very difficult even for powerful
computers (unsolvable, in general). Hence, the rationality assumption
needs justification both for the concept of utility function and for the
algorithms in use. May 2123, 2012 TBA. May 11, 2012, 11:00 Subway networks shape, to some extent, the structure of movements of individuals across a city; similarly, they are being partially shaped by the presence of these individuals in the city. This talk will present two complementary studies describing the dynamic processes which subway networks both host and undergo. May 04, 2012, 11:00 Primitive matrices play an important role in the PerronFrobenius theory and have many applications in the study of Markov chains, page ranking, graphs, optimization, etc. Let us recall that a nonnegative matrix is called primitive if some of its powers is strictly positive. This concept have been extended in the literature to families of nonnegative matrices in many different ways (eventual positivity, mprimitivity, etc.) In contrast to the case of one matrix, when we have a comprehensive description of primitive matrices, the classification of primitive families is usually much more difficult. We introduce the concept of almost primitive families. The family of nonnegative matrices is called almost primitive if there is at least one strictly positive product of these matrices. We show that this concept is quite natural for applications and that many results of the PerronFrobenius theory can be extended for such families. In particular, almost primitive families can be explicitly classified, and the problem of existence of a positive product is decidable by a polynomial algorithm. The total complexity of the algorithm is md^3, where m is the number of matrices and d is the dimension. May 04, 2012, 11:00 A major challenge in singleparticle cryo electronmicroscopy is to establish a reliable abinitio 3D reconstruction using only 2D images without knowing their viewing directions. Reconstruction methods based on commonlines can determine the orientations of images without additional geometric information. However, such reconstruction methods may fail when the commonlines detection rate is low due to the highlevel noise in the images. We present an algorithm for determining the viewing direction of all cryoEM images at once, which is robust to high levels of noise. The algorithm is based on formulating the problem as a synchronization problem, that is, we estimate the relative spatial configuration of pairs of images, and then estimate a global assignment of orientations that satisfies all the pairwise relations. These noisy pairwise relations are combined into a single consistent assignment of orientations by constructing a matrix whose entries encode the pairwise relations. This matrix is shown to have rank 3, and its nontrivial eigenspace is shown to reveal the projection orientation of each image. In particular, we show that the nontrivial eigenvectors encode the rotation matrix that corresponds to each image. April 27, 2012, 11:00 In the IBCNdepartment at Ghent University, our group called DNA (Design of Networking Algorithms) focuses on theoretical developments with practical applications. Recently, we finished a project on dynamic and stochastic routing in networks, which will be highlighted in this talk: industrially driven, the problemsetting crystallizes to some nice datastructures and algorithms, which were then implemented in a production environment, and now deployed by our partnercompany. Apart from that, we will also discuss some other topics on interest and ongoing work at our group. April 20, 2012, 11:00 Distributed computing systems are becoming increasingly large, complex and  at the same time  more and more important for our everyday lives. Designing, managing and reasoning about the structure and dynamics of the underlying communication infrastructures poses enormous challenges in terms of scalability, manageability and robustness. At the same time, the surge of interest in the modeling of large networks and dynamical processes unfolding within them provides valuable insights into the organization of complex systems in nature and society. In this seminar we will discuss how the resulting findings and abstractions can be used constructively in the stochastic management of overlay topologies as well as in the provision of simple decentralized schemes facilitating synchronization and spreading in P2P systems. April 13, 2012, 11:00 Damien Denayer (advisor: Paul Van Dooren): Role models for complex networks March 30, 2012, 11:00 Aurélien Crucifix (advisor: Vincent Blondel): Algorithms for the crowdsourcing problems; March 2729, 2012 TBA. March 22, 2012, 11:00This seminar will be on Thursday The community structure of complex networks reveals both their
organization and hidden relationships among their constituents. Most
community detection methods currently available are not deterministic,
and their results typically depend on the specific random seeds,
initial conditions and tiebreak rules adopted for their execution.
Consensus clustering is used in data analysis to generate stable
results out of a set of partitions delivered by stochastic methods.
Here we show that consensus clustering can be combined with any
existing method in a selfconsistent way, enhancing considerably both
the stability and the accuracy of the resulting partitions. This
framework is also particularly suitable to monitor the evolution of
community structure in temporal networks. An application of consensus
clustering to a large citation network of physics papers demonstrates
its capability to keep track of the birth, death and diversification
of topics. March 16, 2012, 11:00 Complex networks are rarely static, but display dynamics on multiple time scales, and considering the time domain has recently attracted a lot of attention. I will discuss dynamic and temporal features of networks of human communication that reflect the underlying networks of social ties. Such networks display slow dynamics of changes in social ties  relationships growing and waning in strength, ties becoming discontinued, new ties forming  together with very nontrivial shortterm microdynamics of the timings of individual social interaction events. I will address both time scales: related to slow dynamics, I will present recent results on the changes in the social networks of students finishing high school and moving to university, derived from mobile telephone call records. These results show that although there is significant turnover in these networks, individuals display surprisingly persistent call patterns that are in accordance with the layered network view of the social brain hypothesis. Regarding the short time scales, I will discuss the main characteristics of time series of communication events, from burstiness and correlations, and show how they affect networkwide spreading processes and how they translate into mesoscopic temporal patterns in the form of temporal motifs. March 15, 2012, 15:00 TBA. March 9, 2012, 11:00 We propose in this presentation an experimental method to generate random graphs with an arbitrary degree distribution and obeying any additional constraints. It is indeed possible to create a uniformly random sample of a set of such graphs by generalizing usual linkswitching methods. We explore how an experimental process can get us as close as possible to this case. We then consider implementations of these algorithms in various contexts, especially realworld interaction networks. February 24, 2012, 11:00 Current Internet suffers with various scalabilityinduced
problems. We propose in this presentation an interdomain routing
architecture for the Internetlike graph that based on geometry of the
network and solves scalability and policyinduced problems. It introduces
a Geographic routing Control Platform (GCP), which is a logical entity in
each domain for the control of routing and forwarding tasks. This
architecture uses a scalable routing algorithm, which is able to discover
route between given source and destination and chooses the next hop based
on geographic locations of GCP, with the help of a database which map the
address and location of particular GCP. February 17, 2012, 15:00
February 16, 2012, 11:00 This seminar will be on Thursday The simplex algorithm is among the most widely used algorithms for solving linear programs in practice. Most deterministic pivoting rules are known, however, to need an exponential number of steps to solve some linear programs (KleeMinty examples). No nonpolynomial lower bounds on the expected number of steps were known, prior to this work, for randomized pivoting rules. We provide the first subexponential (i.e., of the form 2^(Omega(n^alpha)), for some alpha>0) lower bounds for the two most natural, and most studied, randomized pivoting rules suggested to date. February 10, 2012, 11:00 Several algorithms have been proposed to rank web pages, taking into account the web graph structure. Famous algorithms among them are PageRank, HITS, SALSA and HOTS. We shall focus here on Tomlin's HOTS algorithm, which is a scalable iterative scheme solving a nonlinear network flow problem. The dual solution of this problem, the HOTS score, is then used to rank web pages. An interesting problem in the context of web ranking is the optimization of the score of a web page (or site), given a set of controlled hyperlinks. Whereas PageRank optimization has been studied in several works, the optimization of the HOTS score, and even the convergence of the HOTS algorithm, are less well understood subjects. We prove that the algorithm converges by using nonexpansive mapping techniques and convex optimization techniques. We then address the problem of optimizing the HOTS score of web pages. We give a scalable algorithm based on a low rank property of the matrix of partial derivatives of the objective function. We report numerical results on a fragment of the web graph. February 3, 2012, 11:00 Cancelled and postponed In this talk we present two webbased tools for researchers in graph theory. First, we show how the system GraPHedron allows to derive new conjectures (interactively or automatically) in extremal graph theory. We will briefly survey some theoretical results obtained with the help of GraPHedron. Then a new database of graphs (House of Graphs) will be introduced. The key principle is to have a searchable database and offer – next to complete lists of some graph classes – also a list of special graphs that already turned out to be interesting and relevant in the study of graph theoretic problems (e.g., as extremal graphs or as counterexamples). To build an initial database, we used GraPHedron to generate and solve a set of problems in an automated way. January 27, 2012, 11:00 In the last decade, a significant research activity has developed in the context of complex networks, largely motivated by the fact that many systems can be represented by networks, that is to say a set of sites or vertices connected by ties. After a brief introduction to the field of static complex networks, I will turn to the issue of dynamic complex networks by discussing various examples of infrastructure and social networks. In this context, I will moreover present the project SocioPatterns (http://www.sociopatterns.org/), in which we have developed an infrastructure capable of measuring social interactions in realtime in a limited space, such as a conference, offices, a hospital ... and in which we study the corresponding dynamical social networks. I will present some results obtained by the deployment of this infrastructure, which reveal unexpected regularities in social interactions. I will also present a model of social dynamics that reproduces a number of empirically observed facts. I will conclude with prospects offered by the area of dynamic networks. December 21, 2011, 11:00 Life and language are discrete combinatorial systems (DCSs) in which the basic building blocks are finite sets of elementary units: nucleotides or codons in a DNA sequence and letters or words in a language. Different combinations of these finite units give rise to potentially infinite numbers of genes or sentences. This type of DCS can be represented as an Alphabetic Bipartite Network (αBiN) where there are two kinds of nodes, one type represents the elementary units while the other type represents their combinations. There is an edge between a node corresponding to an elementary unit u and a node corresponding to a particular combination v if u is present in v. Naturally, the partition consisting of the nodes representing elementary units is fixed, while the other partition is allowed to grow unboundedly. The evolution equations for αBiNs under different growth rules are derived, and the corresponding degree distributions computed. It is shown that asymptotically the degree distribution of αBiNs can be described as a family of beta distributions. The onemode projections of the αBiNs and their asymptotics is also studied theoretically and further supported through simulations. December 16, 2011, 11:00 Community finding algorithms for networks have recently been extended to dynamic data. Most of these recent methods aim at exhibiting community partitions from successive graph snapshots and thereafter connecting or smoothing these partitions using clever timedependent features and sampling techniques. These approaches are nonetheless achieving longitudinal rather than dynamic community detection. We assume that communities are fundamentally defined by the repetition of interactions among a set of nodes over time. According to this definition, analyzing the data by considering successive snapshots induces a significant loss of information: we suggest that it blurs essentially dynamic phenomena  such as communities based on repeated intertemporal interactions, nodes switching from a community to another across time, or the possibility that a community survives while its members are being integrally replaced over a longer time period. In this talk, we propose a formalism which aims at tackling this issue in the context of timedirected datasets (such as citation networks), and present several illustrations on both empirical and synthetic dynamic networks. We eventually introduce intrinsically dynamic metrics to qualify temporal community structure and emphasize their possible role as an estimator of the quality of the community detection  taking into account the fact that various empirical contexts may call for distinct `community' definitions and detection criteria. December 8, 2011, 11:00 Ever since Aristotle, organization and classification have been cornerstones of science. In network science, categorization of nodes into modules with communitydetection algorithms has proven indispensable to comprehending the structure of large integrated systems. But in realworld networks, the organization rarely is limited to two levels, and modular descriptions can only provide cross sections of much richer structures. For example, both biological and social systems are often characterized by hierarchical organization with submodules in modules over multiple scales. In many realworld networks, directed and weighted links represent the constraints that the structure of a network places on dynamical processes taking place on this network. Networks thus often represent literal or metaphorical flows: people surfing the web, passengers traveling between airports, ideas spreading between scientists, funds passing between banks, and so on. This flow through a system makes its components interdependent to varying extents. In my talk, I will present our informationtheoretic approach to reveal the multiple levels of interdependences between the nodes of a network. I will also present a straightforward generalization to overlapping modules and discuss recent results on efficient modeling of the underlying dynamics on networks. December 2, 2011, 11:00 A gently introduction to the concept of communicability from a combinatorial perspective. We then make some links with the physics of classical and quantum harmonic oscillators. We analyse the use of communicability functions for detecting communities in networks and given some examples of applications. The analysis of selfcommunicability or subgraph centrality is then motivated and some examples are provided for the study of protein interaction networks. Finally the possibilities of communicability functions for studying brain networks are summarized. November 29, 2011, 09:30 9:30 Registration November 25, 2011, 11:00 Collective behavior and social dynamics have recently been studied in many fields of science using methods from statistical physics in order to describe selforganized, emergent phenomena by theoretical models. However an evident lack of empirical studies, especially in the field of collective behaviour of human beings can be observed. The main reason for this is the immanent difficulty to achieve information about the social connections between humans while observing collective processes in traditional experiment settings. Today, the existence of largescale social online networks for the first time provides the opportunity of largescale studies on human's collective behavior in consideration of the underlying social network structure. In this regard socalled collaborative social online games based on common social network services can be a useful tool for largescale empirical studies in the field of social dynamics. Collaborative social online games feature a novel game principle where users do not act as individuals on their own account. Instead, users have to collaborate in large groups of similar entities based on local knowledge and local interaction facilities only. This talk gives an inside to the idea of utilizing collaborative social online games for studies on collective behavior and gives an overview of the ongoing work in this interdisciplinary field at the University of Luxembourg. November 18, 2011, 11:00 The use mathematical physics is today a well accepted framework where model and study social phenomena. After an initial phase relying
mostly on qualitative models, scientists begun to obtain quantitative
results. The aim of those quite abstract models is mainly to capture
universal pattern in human behaviors without carefully adding
complicating details that could blind a complete understanding of the
assumptions done. November 7, 2011, 14:00 This seminar will be given in on Monday Association networks represent systems of interacting elements, where a link between two different elements indicates a sufficient level of similarity between element attributes. While in reality relational ties between elements can be expected to be based on similarity across multiple attributes, the vast majority of work to date on association networks involves ties defined with respect to only a single attribute. We propose an approach for the inference of multiattribute association networks from measurements on continuous attribute variables, using canonical correlation and a hypothesistesting strategy. Within this context, we then study the impact of partial information on multiattribute network inference and characterization, when only a subset of attributes is available. We examine through a combination of analytical and numerical techniques the implications of the choice and number of node attributes on the ability to detect network links and, more generally, to estimate higherlevel network summary statistics, such as node degree, clustering coefficients, and measures of centrality. We consider in detail the case of two attributes and discuss generalization of our findings to more than two attributes. Our work is motivated by and illustrated within the context of gene/protein regulatory networks in human cancer cells. Joint work with Natallia Katenka. November 04, 2011, 11:00 Without having direct access to the information that is being exchanged, traces of information flow can be obtained by looking at temporal sequences of user interactions. These sequences can be represented as causality trees whose statistics result from a complex interplay between the topology of the underlying (social) network and the time correlations among the communications. I will show that causality trees in mobilephone data can be represented as a dynamical directed network. This representation of the data reveals the existence of superspreaders and superreceivers. I will show that the tree statistics, respectively the information spreading process, are extremely sensitive to the inout degree correlation exhibited by the users. Moreover, I would explain that a given information, e.g., a rumor, would require users to retransmit it for more than 30 hours in order to cover a macroscopic fraction of the system. Our analysis indicates that topological nodenode correlations of the underlying social network, while allowing the existence of information loops, they also promote information spreading. Temporal correlations, and therefore causality effects, are only visible as local phenomena and during short time scales. These results are obtained through a combination of theory and data analysis techniques. October 21, 2011, 11:00 Several infections are transmitted through interactions between individuals. These interactions form contact networks with nontrivial structural and temporal patterns. These patterns affect the propagation of infections and as such, need to be considered to better understand the emergence of epidemics and to control them. In this talk, I first introduce and discuss some properties of a large empirical temporal network of sexual contacts, obtained from a web community related to sexual encounters between sexbuyers and sellers. Afterwards, I present some results about the simulation of general STIs on this evolving network and discuss how the infection patterns change due to not only the temporal constraints but also due to cluster structures, and finally I present some results about vaccination protocols based on temporal information and discuss their efficiency in diverse networks related to human interaction. 