We are interested in all aspects of real world networks and their models, from internet measurements to random graphs, from social network analysis to spreading phenomena, and from graph algorithms to biological networks.
Alice Albano
JFGG 2011
Les phénomènes de diffusion sont présents dans de nombreux contextes: diffusion d’épidémies, de virus informatiques, d’information dans des réseaux sociaux, etc. Bien que les réseaux où se produit la diffusion soient souvent dynamiques, cette dynamique n’est pas prise en compte dans la plupart des modèles existants. L’objectif de ces travaux est de proposer des modèles de diffusion, et d’étudier l’impact de la dynamique du réseau sur la diffusion.
Oussama Allali, Clémence Magnien and Matthieu Latapy
Dynamic Networks and Knowledge Discovery, special issue of Intelligent Data Analysis, 7 (1), 5-25, 2013
Many real-world complex networks, like actor-movie or le-provider relations, have a bipartite nature and evolve over time. Predicting links that will appear in them is one of the main approach to understand their dynamics. Only few works address the bipartite case, though, despite its high practical interest and the specic challenges it raises. We dene in this paper the notion of internal links in bipartite graphs and propose a link prediction method based on them. We thoroughly describe the method and its variations, and experimentally compare it to a basic collaborative ltering approach. We present results obtained for a typical practical case. We reach the conclusion that our method performs very well, and we study in details how its parameters may inuence obtained results.
Thomas Aynaud
Jeudi 29 Septembre 2011, 11h, salle 26-00/101
Dans la plupart des graphes de terrain, il existe des groupes de noeuds fortement liés entre eux mais peu à l’extérieur, appelés des communautés et leur identification est importante dans de nombreux contextes pour décrire la structure du graphe. Nous étudierons la détection de ces communautés dans le cas de graphes dynamiques. Premièrement, nous détecterons des communautés à chaque instant, ce qui pose des problèmes de stabilité. Ensuite, nous définirons des communautés pertinentes sur une longue durée et proposerons une méthode pour trouver les durées intéressantes. Nous verrons enfin des applications à la détection d’événements et à la segmentation de vidéos.
Thomas Aynaud and Jean-Loup Guillaume
proceedings of the Fifth SNA-KDD Workshop Social Network Mining and Analysis, in conjunction with the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2011)
Many complex systems composed of interacting objects like social networks or the web can be modeled as graphs. They can usually be divided in dense sub-graphs with few links between them, called communities and detecting this underlying community structure may have a major impact in the understanding of these systems. We focus here on evolving graphs, for which the usual approach is to represent the state of the system at different time steps and to compute communities independently on the graph obtained at each time step. We propose in this paper to use a different framework: instead of detecting communities on each time step, we detect a unique decomposition in communities that is relevant for (almost) every time step during a given period called the time window. We propose a definition of this new decomposition and two algorithms to detect it quickly. We validate both the approach and the algorithms on three evolving networks of different kinds showing that the quality loss at each time step is very low despite the constraint of maximization on several time steps. Since the time window length is a crucial parameter of our technique, we also propose an unsupervised hierarchical clustering algorithm to build automatically a hierarchical time segmentation into time windows. This clustering relies on a new similarity measure based on community structure. We show that it is very efficient in detecting meaningful windows.
Adrien Friggeri, Jean-Philippe Cointet and Matthieu Latapy
Complex Systems 19, 2011
We designed an experiment to observe a spreading phenomenon in the blogosphere. This experiment relies on a small applet that participants copy on their own web page. We present the obtained dataset, which we freely provide for study, and conduct basic analysis. We conclude that, despite the classical assumption, in this experiment famous blogs do not necessarily act as super spreaders.
Pascal Pons, Matthieu Latapy
Theoretical Computer Science (TCS) 412(8-10): 892-900 (2011)
Dense sub-graphs of sparse graphs (communities), which appear in most real-world complex networks, play an important role in many contexts. Most existing community detection algorithms produce a hierarchical structure of communities and seek a partition into communities that optimizes a given quality function. We propose new methods to improve the results of any of these algorithms. First we show how to optimize a general class of additive quality functions (containing the modularity, the performance, and a new similarity-based quality function which we propose) over a larger set of partitions than the classical methods. Moreover, we define new multi-scale quality functions which make it possible to detect different scales at which meaningful community structures appear, while classical approaches find only one partition.
Matthieu Latapy, Clémence Magnien and Frédéric Ouédraogo
Complex Systems, 20 (1), 23-30, 2011.
Mapping the internet’s topology is a challenge in itself, and studying its dynamics is even more difficult. Achieving this would however provide key information on the nature of the internet, crucial for modeling and simulation. Moreover, detecting anomalies in this dynamics is a key issue for security. We introduce here a new measurement approach which makes it possible to capture internet dynamics at a scale of a few minutes in a radar-like manner. By conducting and analyzing large-scale measurements of this kind, we rigorously and automatically detect events in the observed dynamics, which is totally out of reach of previous approaches.
Oussama Allali, Clémence Magnien and Matthieu Latapy
Proceedings of the third International Workshop on Network Science for Communication Networks (Netscicom 2011), In conjunction with IEEE Infocom 2011.
Many real-world complex networks, like client-product or file-provider relations, have a bipartite nature and evolve during time. Predicting links that will appear in them is one of the main approach to understand their dynamics. Only few works address the bipartite case, though, despite its high practical interest and the specific challenges it raises. We define in this paper the notion of internal links in bipartite graphs and propose a link prediction method based on them. We describe the method and experimentally compare it to a basic collaborative filtering approach. We present results obtained for two typical practical cases. We reach the conclusion that our method performs very well, and that internal links play an important role in bipartite graphs and their dynamics.
Matthieu Latapy, Clémence Magnien and Raphaël Fournier
IEEE Infocom Mini-Conference 2011, Shanghai
Increasing knowledge of paedophile activity in P2P systems is a crucial societal concern, with important consequences on child protection, policy making, and internet regulation. Because of a lack of traces of P2P exchanges and rigorous analysis methodology, however, current knowledge of this activity remains very limited. We consider here a widely used P2P system, eDonkey, and focus on two key statistics: the fraction of paedophile queries entered in the system and the fraction of users who entered such queries. We collect hundreds of millions of keyword-based queries; we design a paedophile query detection tool for which we establish false positive and false negative rates using assessment by experts; with this tool and these rates, we then estimate the fraction of paedophile queries in our data; finally, we design and apply methods for quantifying users who entered such queries. We conclude that approximately 0.25 % of queries are paedophile, and that more than 0.2 % of users enter such queries. These statistics are by far the most precise and reliable ever obtained in this domain.
Marie-Aude Aufaure
16 juin 2011 à 11h : salle 25-26/101
Business Intelligence aims at supporting better business decision-making, by providing tools and methods for collecting, modeling and interacting with data. Users have to deal with big data from structured databases and unstructured content (emails, documents, social networks, etc). Moreover, these data are often distributed and highly dynamic. Social Media and mobile technologies have changed our way to access information, facilitating communication and data exchange/sharing. All these evolutions refer to Business Intelligence 2.0. An adapted modeling and visualization technique of links and interactions between several objects (e.g. products and sites, customers and products, social network…) is a precious mean to permit a good understanding of a lot of situations in the enterprise context. In this latter context, most of the time, these objects and their relations are stored in relational databases. But extracting and modeling such heterogeneous graphs, with heterogeneous objects and relations, are outside of the classical graph models capabilities, moreover when each node contains a set of values. On the other hand, graph models can be a natural way to present these interactions and to facilitate their querying. In this way, we propose a graph model named SPIDER-Graph which is adapted to represent interactions between complex heterogeneous objects extracted from relational databases, used for heterogeneous objects graph extraction from a relational database. One of the steps involved in this approach consists in identifying automatically the enterprise objects. Since the enterprise ontology has been used for describing enterprise objects and processes, we propose to integrate it in the object identification process (identify objects to be able to transform a graph of heterogeneous objects according to the user choice). Finally, we introduce the main principles of an aggregation algorithm used for community detection and graph visualization.
Binh-Minh Bui-Xuan
7 avril 2011 à 11h : salle 25-26/101
Decomposition is a technical term that, from an algorithmic point of view, refers to the act of dividing an input instance into simpler pieces. Popular examples of decomposition include Merge-Sort and the factorization of polynomials. Decomposition is fundamental for divide-and-conquer algorithms, and variants such as dynamic programming. We first present a generic approach to design efficient decomposition algorithms on graphs, that will be expressed under the light of combinatorial optimisation over set famillies. We show how to apply the machinery on several old and new notions of decomposition. These decomposition notions can be extended so that NP-complete graph problems can be tackled within a reasonable (parameterized) runtime. To this aim we discuss on what can be qualified as two natural ways to generalise a particularly classical notion, the modular decomposition of graphs. One is tightly bound to a well-known topic in algorithmic graph theory called width parameters. The other links to recent works in clustering, social networks, complex systems, etc.
Franck Ghitalla
19 mai 2011 à 11h : salle 25-26/101
Au delà des graphes et des méthodes de leur visualisation, la cartographie de l’information représente un univers original qui a ses propres contraintes. L’exposé sera l’occasion de présenter les principales dimensions de la cartographie d’information, à partir d’exemples commentés.
Jean-Daniel Fekete
24 février 2011 à 11h : salle 25-26/101
Les réseaux sont des objets complexes qui peuvent être analysés et explorés, généralement à laide de visualisation. Jusquà présent, la grande majorité des outils de visualisation utilise la représentation par nœuds et liens : les sommets sont représentés par des nœuds et les arcs par des lignes. Cette représentation est familière mais elle devient illisible lorsque le réseau devient dense. Alternativement, il est possible dafficher la matrice dadjacence du réseau en plaçant les sommets en lignes et colonnes et les liens en cellules à lintersection de ces lignes et colonnes. Une cellule est marquée lorsquun arc existe entre le somme de la ligne et celui de la colonne. Cette représentation est moins familière mais reste lisible même lorsque la densité du réseau augmente. Ces dernières années, la représentation matricielle a été beaucoup étudiée : nous allons présenter les divers solutions proposées pour visualiser, ordonner et naviguer dans ces matrices dadjacence, ainsi que les représentations mélangeant matrices avec nœuds et liens.
Mario Chavez
27 janvier 2011
Electroencephalography, magnetoencephalography, or functional magnetic resonance imaging (fMRI) techniques are currently used to estimate functional connectivity patterns between different brain areas. In this talk I’ll show how a complex network description might provide new insights into the understanding of human brain connectivity during different pathological and cognitive neuro-dynamical states.
Laurent Viennot
16 décembre 2010
tant donné un graphe G, un spanner est un sous graphe H qui couvre tous les sommets de G. On s’intéresse alors à deux paramètres : la distance dans H par rapport à la distance dans G, et la taille de H en nombre d’arêtes. L’optimisation simultanée de ces deux paramètres conduit à des compromis que nous mettrons en évidence.
Juan David Cruz-Gomez
03 décembre 2010
Classic algorithms for community detection in social networks use the structural information to identify groups in the social network, i.e., how clusters are formed according to the topology of the relationships. However, these methods don’t take into account any semantic information which could guide the clustering process, and which may add elements to do further analyses. The method we propose, uses in a conjoint way, the semantic information from the social network, represented by the point of view, and its structural information. This is, by the combination of the relationships, expressed by the edges on one hand, and the implicit relations deduced from the semantic information on the other hand.
Dmitri Krioukov
07 juillet 2010
We establish a connection between the scale-free topology of complex networks, and the hyperbolic geometry of hidden metric spaces underlying these networks. Given a hyperbolic space, networks topologies with scale-free degree distributions and strong clustering naturally emerge on top of the space as topological reflections of its hyperbolic geometry. Conversely, for any scale-free network with strong clustering, there is an effective hyperbolic space underlying the network. The underlying hyperbolic geometry enables greedy routing with optimal efficiency. Greedy routing does not require any global information about network topology to navigate the network. At each hop, greedy routing selects as the next hop the current hop neighbor closest to the destination in the underlying hyperbolic space. We show that in complex networks mapped to their hyperbolic spaces, greedy routing always succeeds reaching the destination, following the topologically shortest paths. Furthermore, we show that even without re-mapping the network or changing any node coordinates, this navigation efficiency is remarkably robust with respect to rapid network dynamics, and catastrophic levels of network damage. We map the real Internet AS-level topology to its hyperbolic space, and find that greedy routing using this map exhibits similar efficiency. These results effectively deliver a solution for Internet interdomain routing with theoretically best possible scaling properties. Not only routing table sizes and stretch are as small as possible, but also routing communication overhead is reduced to zero.
Shaowen Qin
17 juin 2010
We present a study on clustering of software classes based on software execution data, which offers a dynamic, hence more realistic, perspective to the understanding of software structure and the evaluation and improvement of the existing architectural design. The approach first uses association rule mining to extract low-level class relations in object-oriented software. The mining results are then processed by hypergraph-based clustering to identify an optimal set of high-level clusters of classes that have relatively high cohesion within and low coupling between them. It is also shown that such clusters are actually unique. The identified clusters can be seen as execution components of the software, which represents the effect, rather than the intention of the existing design. Two case studies are presented to demonstrate the application of our approach. Relevant concepts in complex network are also introduced to interpret the findings of this study
Jussara Almeida
10 juin 2010
A number of online video social networks, out of which YouTube is the most popular, provides features that allow users to post a video as a response to a discussion topic. These features open opportunities] for users to introduce polluted content into the system. For instance, spammers may post an unrelated video as response to a popular one aiming at increasing the likelihood of the response being viewed by a larger number of users. Moreover, opportunistic users – promoters – may try to gain visibility to a specific video by posting a large number of (potentially unrelated) responses to boost the rank of the responded video, making it appear in the top lists maintained by the system. In this talk, I will present some of our initial results on detecting spammers and content promoters on YouTube. Our study is based on a characterization of several properties associated with YouTube users as well as the use of state-of-the-art classification algorithms.