François Queyroi, Sergey Kirgizov

Information Processing Letters, Volume 115, Issue 9, September 2015, Pages 689–693 http://www.sciencedirect.com/science/article/pii/S0020019015000678

We discuss  the computation  of a  distance between  two hierarchical clusterings of the  same set. It is defined as  the minimum number of  elements that  have to  be removed so  the remaining  clusterings are  equal. The problem of distance  computing was extensively studied for partitions. We prove it can be  solved in polynomial time in the case of hierarchies  as it gives  birth to a  class of perfect  graphs. We  also  propose an  algorithm  based on  recursively computing  maximum assignments.

Download

Tiphaine Viard, Matthieu Latapy et Clémence Magnien

ALGOTEL 2015 — 17èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, juin 2015, Beaune, France

Un flot de liens est une séquence de triplets (t,u,v), signifiant que u et v ont interagi au temps t. Nous généralisons la notion de cliques à ces flots de liens : pour un delta donné, une delta-clique est un ensemble de nœuds et un intervalle de temps, tels que toutes les paires de nœuds dans cet ensemble interagissent au moins tous les delta sur cet intervalle. Nous proposons un premier algorithme permettant d’énumérer les delta-cliques dans un flot de liens.

Download

Soumajit Pramanik, Maximilien Danisch, Qinna Wang and Bivas Mitra

[extended abstract] Twitter for Research, 1st International & Interdisciplinary Conference, 2015

We developed a Twitter app to suggest users to mention in a tweet in order to maximise the spread of an information. Users that are popular, active on Twitter and interested in the content of the tweet are targeted. The problem is mapped to the knapsack problem, the length of the screen name of a user being an important variable. Collected data (who retweets among the suggested users and features of these users) will be used to improve the app and theory/models of information spread on Online Social Networks. The application is available at: http://bit.ly/1BKZURE

Download

Christophe Crespelle, Matthieu Latapy, Ha Duong Phan.

Discrete Applied Mathematics, Volume 195, 20 November 2015, Pages 59–73

We define a new graph operator, called the weak-factor graph, which comes from the context of complex network modelling. The weak-factor operator is close to the well-known clique-graph operator but it rather operates in terms of bicliques in a multipartite graph. We address the problem of the termination of the series of graphs obtained by iteratively applying the weak-factor operator starting from a given input graph. As for the clique-graph operator, it turns out that some graphs give rise to series that do not terminate. Therefore, we design a slight variation of the weak-factor operator, called clean-factor, and prove that its associated series terminates for all input graphs. In addition, we show that the multipartite graph on which the series terminates has a very nice combinatorial structure: we exhibit a bijection between its vertices and the chains of the inclusion order on the intersections of the maximal cliques of the input graph.

Download

Noé Gaumont, François Queyroi, Clémence Magnien et Matthieu Latapy.

In Complex Networks VI (pp. 57-64). Springer International Publishing. 2015

Many studies use community detection algorithms in order to understand complex networks. Most papers study node communities, i.e. groups of nodes, which may or may not overlap. A widely used measure to evaluate the quality of a community structure is the modularity. However, sometimes it is also relevant to study link partitions rather than node partitions. In order to evaluate a link partition, we propose a new quality function: Expected Nodes. Our function is based on the same inspiration as the modularity and compares, for a given link group, the number of incident nodes to the expected one. In this short note, we discuss the advantages and drawbacks of our quality function compared to other ones on synthetics graphs. We show that Expected Nodes is able to pass some fundamental sanity criteria and is the one that best identifies the most relevant partition in a more realistic context.

Download

Noé Gaumont, François Queyroi

ALGOTEL 2014 — 16èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Jun 2014, Le Bois-Plage-en-Ré, France. pp.1-4

La recherche de communautés chevauchantes est un enjeu important pour l’analyse des réseaux complexes. Une piste souvent envisagée est la recherche d’un partitionnement des arêtes du graphe. L’évaluation de cette décomposition tient cependant rarement compte du fait que les communautés recherchées correspondent à des groupes d’arêtes. Nous discutons dans ce papier l’utilisation de nouveaux critères pouvant répondre à ce problème. Nous proposons de comparer le nombre de sommets incidents à un groupe d’arêtes au nombre attendu dans un graphe aléatoire. Un optimum local de la mesure dérivée de ce concept peut être obtenu par un algorithme glouton. Nous présentons les premiers résultats obtenus à travers une analyse de la mesure et des tests empiriques.

Download

François Queyroi

5ème conférence sur les Modèles et l’Analyse des Réseaux : Approches Mathématiques et Informatique (MARAMI), Paris, 2014.

Nous présentons une transformation de graphes temporels, appelée -duplication, permettant de réduire l’hétérogénéité temporelle dans l’analyse de réseaux dynamiques. Au lieu de construire une séquence d’instantanées à partir d’un découpage global du temps, nous utilisons une approche centrée sur les individus en considérant un sommet sur plusieurs sessions i.e. des périodes durant lesquelles il se connecte au moins tous les . Cette note décrit précisément le concept de -duplication et fournit des pistes quant à son utilisation pour l’analyse de réseaux complexes. En particulier, nous proposons une généralisation du concept de k-cores aux graphes temporels.

Tackx Raphaël, Maximilien Danisch et Fabien Tarissan

In Acte de la 5ème Conférence sur les Modèles et l’Analyse des Réseaux : Approches Mathématiques et Informatique (MARAMI’14), Paris, France, 2014.

De nombreux réseaux rencontrés en pratique se prêtent naturellement à la formalisation sous forme de graphes pour analyser et modéliser leur structure. Cette représentation plate des réseaux s’est montrée cependant peu efficace pour rendre compte de propriétés importantes et non triviales liées à la structure bipartie des réseaux. Des travaux récents ont montré notamment que des propriétés de recouvrements semblaient être présentes dans la plupart des réseaux réels et qu’elles permettaient de mieux expliquer des propriétés observées sur dans les graphes simples. Le présent travail entend poursuivre cette problématique en étudiant les propriétés liées aux recouvrements dans les structures communautaire des réseaux sociaux. Nous conduisons pour cela une étude basée sur le réseau des pages et catégories WIKIPEDIA et nous montrons notamment que parmi les métriques proposées récemment pour rendre compte de ces recouvrements complexes entre communautés, le coefficient de redondance était plus pertinent que le populaire coefficient de clustering biparti étudié généralement en pratique.

Download

Fabien Tarissan

In ISCS 2014: Interdisciplinary Symposium on Complex Systems, Emergence, Complexity and Computation, 14:309-318, Springer, 2014.

Many real-world networks lend themselves to the use of graphs for analysing and modelling their structure. But such a simple representation has proven to miss some important and non trivial properties hidden in the bipartite structure of the networks. Recent papers have shown that overlapping properties seem to be present in bipartite networks and that it could explain better the properties observed in simple graphs. This work intends to investigate this question by studying two proposed metrics to account for overlapping structures in bipartite networks. The study, conducted on four dataset stemming from very different contexts (computer science, juridical science and social science), shows that the most popular metrics, the clustering coefficient, turns out to be less relevant that the recent redundancy coefficient to analyse intricate overlapping properties of real networks.

Download

Romain Hollanders, Daniel Bernardes, Bivas Mitra, Raphael Jungers, Jean-Charles Delvenne, Fabien Tarissan.

In Journal of Network Science, 2(3):341-266, Cambridge University Press, 2014.

Peer-to-peer (p2p) systems have driven a lot of attention in the past decade as they have become a major source of Internet traffic. The amount of data flowing through the p2p network is huge and hence challenging both to comprehend and to control. In this work, we take advantage of a new and rich dataset recording p2p activity at a remarkable scale to address these difficult problems. After extracting the relevant and measurable properties of the network from the data, we develop two models that aim to make the link between the low-level properties of the network, such as the proportion of peers that do not share content (i.e., free riders) or the distribution of the files among the peers, and its high-level properties, such as the Quality of Service or the diffusion of content, which are of interest for supervision and control purposes. We observe a significant agreement between the high-level properties measured on the real data and on the synthetic data generated by our models, which is encouraging for our models to be used in practice as large-scale prediction tools. Relying on them, we demonstrate that spending efforts to reduce the amount of free-riders indeed helps to improve the availability of files on the network. We observe however a saturation of this phenomenon after 65% of free-riders.

Download

Matthieu Latapy, Elie Rotenberg, Christophe Crespelle, Fabien Tarissan

13th IFIP International Conference on Networking – Networking 2014, 2014, Trondheim, Norway. IEEE, pp.1-9

Most current models of the internet rely on knowledge of the degree distribution of its core routers, which plays a key role for simulation purposes. In practice, this distribution is usually observed directly on maps known to be partial, biased and erroneous. This raises serious concerns on the true knowledge one may have of this key property. Here, we design an original measurement approach targeting reliable estimation of the degree distribution of core routers, without resorting to any map. It consists in sampling random core routers and precisely estimate their degree thanks to probes sent from many distributed monitors. We run and assess a large-scale measurement following this approach, carefully controlling and correcting bias and errors encountered in practice. The estimate we obtain is much more reliable than previous knowledge, and it shows that the true degree distribution is very different from all current assumptions.

Download

Fabien Tarissan, Elie Rotenberg, Matthieu Latapy, Christophe Crespelle

IEEE 22nd International Symposium on Modeling Analysis and Simulation of Computer and Telecomunication Systems (MASCOTS’14), At Paris, France

The classical approach for Internet topology measurement consists in distributively collecting as much data as possible and merging it into one single piece of topology on which are conducted subsequent analysis. Although this approach may seem reasonable, in most cases network measurements performed in this way suffer from some or all of the following limitations: they give only partial views of the networks under concern, these views may be intrinsically biased, and they contain erroneous data due to the measurement tools. Here we present a new tool, named UDP Ping , that relies on a very different approach for the measurement of the Internet topology. Its basic principle is to measure the interface of a given target directed toward a monitor which sends the measurement probe. We demonstrate how to use it to deploy real world-wide measurements that provide reliable (i.e. bias and error free) knowledge of the Internet topology, namely the degree distribution of routers in the core Internet in our example.

Download