Today's technology is producing data at an ever increasing rate, and part if this data can be modeled as graphs: a set of nodes (or “vertices”), and links (or “edges”) between nodes. Here are a few examples:
| System | Nodes | Links |
|---|---|---|
| users | friendships | |
| Telephone | subscribers | calls |
| Economy | firms | transactions |
| Genome | genes | activations or inhibitions |
| Linguistics | words | synonyms |
| Road network | cities | roads |
| Scientometry | articles | citations |
| ... | ... | ... |
In 1967, Milgram observed that almost anyone can be reached through a short chain of social acquaintances, despite the fact that the world population is huge. This is the small world effect. Not only this social network, but practically all real networks have this property. Another common point of those networks is the existence of a few hubs with a disproportionately large number of connections (think of London's airports) and many small nodes. Thanks to a few more common properties, it is thus relevant to design common methods to apply to all those networks: this is done mainly by mathematicians, physicists, computer scientists, while the study of specific networks are done by specialists like biologists, linguists, geographers, etc.
Complex network theory can be structured in five branches:
- metrology: collect dynamical and reliable data at large scale
- analysis: describe a graph and extract relevant information
- modeling: reproduce in a formal model the observed properties to explain and prove them, and to conduct simulations
- algorithms: compute the parameters defined in the analysis phase. The huge size of the graphs (up to hundreds of millions of nodes) forbids some classical algorithms. On the other hand, the specific structure of complex networks can help design specialized algorithms.
- visualization: represent the graph and associated data to allow efficent exploration and understanding of its structure.
Example applications include:
- Given the record of all calls placed among the subscribers of a mobile phone company, find the nodes (i.e. the users) most likely to switch to a competitor. Or find the local leaders: if we give a new product to them, all their friends will want to buy the same product.
- Given a network of genes and interactions, find the genes that work together, to suggest unexpected relations and new biological experiments.
- When studying the propagation of a virus (be it a biological one or a computer virus), find the nodes that should be immunized in order to block the propagation. Or if it is about a rumor (like "My product is the best"), maximize the propagation.
I work on networks arising in various (quite different) domains, specifically on communities, structure, dynamics. I have an interest for large datasets (for instance, I have worked on the Vélo'v / Vélib network, and on co-authorship networks.)
My publications list is here
Links
- Roadmap from the complex systems society (to which I contributed)
- A few French (or partly French) teams working mainly on complex networks:
- Complex Networks (in Paris)
- Cx-Nets (a group of 3 labs, one in Marseille)
- D-NET (in Lyon)
- GRAVITE (in Bordeaux)
- AVIZ (in Saclay, South of Paris)
- SocioPatterns
- GVSR: comparison of graph visualization softwares