France: PhD Position in Complex Networks

Font size: Decrease font Enlarge font

ENS Lyon and the A4RES team at INRIA have received a grant to fund a studentship for research into complex networks. The studentship is fully funded by French Ministry of research for three years. The A4RES team at INRIA and LIP (ENS Lyon, France) invites applications from outstanding candidates for a PhD  research position.

PhD Title: Detecting dynamic communities in large scale dynamic networks

Complex networks play an important role in several scientific contexts: computer science, social and interaction networks or epidemiology. Typical examples of such networks are the Internet, web graphs, E-mail, phone calls, P2P networks, etc. In these networks, links between entities generally represent some kind of interaction. Studied as a whole, these networks exhibit nontrivial properties in common and some problems span over a large variety of networks. For instance, the spreading of information is studied in computer science but also in epidemiology and the detection of dense subnetworks (communities) is also a problem having strong implications in many domains. Last decade, this domain has proposed a large set of tools which can be used on any complex network in order to get a deep insight on its properties and to compare it to other networks (see for instance [2] for a review of parameters).

However, one fundamental property has until recently be understudied. Complex networks evolve: new nodes and edges appear while some old ones disappear. These evolutions are often playing a key role in all the scientific domains cited above: people added or removed on the Internet, etc. If some studies are dedicated to the dynamics of complex networks [8,11,13] they are still too few. It appears crucial to better understand the evolution of these networks first to get knowledge but also to be able to generate random evolving networks which can be used for simulation purposes

One may imagine several distinct approaches to study complex networks : (1) it is possible to describe the evolution of a network as a sequence of static networks and since there exist many parameters to describe accurately a static network, one can study the evolution of the network through the evolution of these parameters; (2) one can study the evolution itself and define parameters to capture it, such as the rate of apparition or disappearance of nodes and edges; (3) An intermediate approach can be used which consists in studying specific phenomena or users of interest through time…

The main challenge is to setup a theoretical framework and to identify to theoretical tools suitable for describing the relevant observables that will catch the important characteristics, to model the dynamic of large scale networks and to define the notion of complexity of such dynamic networks:

* One may try to propose a valuable definition and characterization of dynamic communities which play an important role for information dissemination. The main challenge is to propose a definition that captures the intrinsic notion of the dynamic.

* Define a suitable distance and space in order to specify dense zone in a dynamic network in order to be able to study the Reny entropy in such context.

* Study the notion of Kolmogorov Complexity applied to dynamic graphs.

Expected outcomes should be both theoretical (algorithm design and proofs) and practical (simulation on large traces) in order to fully validate the proposed solutions. (Data will come from the IP LSH MOSAR project


The candidate is expected to work on a theoretical and applied line. He/She should be able to perform good critical analyzes of obtained results and be creative in proposing solutions. A strong background on graph, complex networks, and algorithm design is required. Additional skills in Complexity, Rényi entropy, time–frequency analysis, Kologorov Complexity is a real advantage.

Candidates are encouraged to send an email with Curriculum
Vitae, including their academic record, to Prof. Eric Fleury
before September 15, 2008. Please also feel free to
contact us for further information.

Prof. at ENS Lyon
TEL: +33 (0)672 162 974

[1] A. Scherrer, P. Borgnat, E. Fleury, J.-L. Guillaume and C. Robardet, Analysis and Simulation of Dynamic Interaction Networks, Computer Network, 2008
[2] R. Albert and A.-L. Barabási. Statistical mechanics of complex networks. Reviews of Modern Physics 74, 47, 2002.
S.N. Dorogovtsev and J.F.F. Mendes. Handbook of Graphs and Networks: From the Genome to the Internet, chapter Accelerated growth of networks. Wiley-VCH, 2002.
[5] A. Chaintreau, P. Hui, J. Crowcroft, C. Diot, R. Gass, and J. Scott. Impact of human mobility on the design of opportunistic forwarding algorithms. In INFOCOM, 2006.
[6] D. Chakrabarti, R. Kumar, and A. Tomkins. Evolutionary clustering. In KDD ’06: Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 554–560. ACM, 2006.
[7] Y. Chi, S. Zhu, X. Song, J. Tatemura, and B.L. Tseng. Structural and temporal analysis of the blogosphere through community factorization. In KDD ’07: Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 163–172. ACM Press, 2007.
[9] E. Fleury, J.-L. Guillaume, C. Robardet, and A. Scherrer. Analysis of dynamic sensor networks: Power law then what? In Second International Conference on COMmunication Systems softWAre and middleware (COMSWARE 2007), Bangalore, India, 2007. IEEE.
[10] J. Leskovec, L.A. Adamic, and B.A. Huberman. The dynamics of viral marketing. In EC ’06: Proceedings of the 7th ACM conference on Electronic commerce, pages 228–237. ACM Press, 2006.
[11] J. Leskovec, J. Kleinberg, and C. Faloutsos. Graphs over time: Densification laws, shrinking diameters and possible explanations. In ACM SIGKDD, 2005.
[12] J. Leskovec, M. McGlohon, C. Faloutsos, N. Glance, and M. Hurst. Cascading behavior in large blog graphs, 2007.
[13] G. Palla, A. Barabasi, and T. Vicsek. Quantifying social group evolution. Nature, 446:664–667, April 2007.
[14] Y. Wang, D. Chakrabarti, C. Wang, and C. Faloutsos. Epidemic spreading in real networks: An eigenvalue viewpoint. In 22nd Symposium on Reliable Distributed Computing, 2003.
[15] J.D.Watts and S.H. Strogatz. Collective dynamics of’small-world’networks. Nature, 393(6684):409–10, 1998.

Be Sociable, Share!

No Comments

Post your comment comment

You must be logged in to post a comment.