By admin | Published: January 26, 2010
Massoud Seifi, Jean-loup Guillaume, Matthieu Latapy and Bénédicte Le Grand
De nombreux réseaux du monde réel peuvent être modélisés par des
grands graphes. Réduire la complexité d'un graphe de manière à ce qu'il puisse
être facilement interprété par l'oeil humain est une aide précieuse pour comprendre et analyser ce type de données. Nous proposons une méthodologie de
visualisation interactive multi-échelle de grands graphes basée sur une classification des sommets qui nous permet de représenter ces graphes de manière lisible et interprétable. Nous appliquons notre méthodologie à un réseau de blogs
francophones.
Posted in Papers | Also tagged blogs, visualization
By admin | Published: May 2, 2009
> By Thomas Aynaud and Jean-Loup Guillaume To study the communities dynamics and stability, we have taken a network representing the co-authorship of scientists on www.arxiv.org and we have successively removed one random node and kept the biggest connected component. At each step, we have detected the communities in two ways. We have, first, used [...]
Posted in Plots | Also tagged dynamics
By admin | Published: April 4, 2009
> By Jean-Loup Guillaume Many community detection algorithms are non deterministic and can therefore give different partitions for the same graph. Depending on the context, it can be important to obtain stable results so as to identify very pertinent communities, but it can also be interesting to find some less stable ones. For non deterministic [...]
Posted in Plots | Tagged communities
By admin | Published: February 28, 2009
> By Jean-Loup Guillaume Community detection in complex networks is a hard problem whose classical formulation is the maximisation of the modularity. Since this problem cannot be solved exactly in a reasonable time, heuristics are used to find the best communities. The Louvain method is an efficient technique to study this problem and consists in [...]
Posted in Plots | Also tagged modularity
By admin | Published: February 13, 2009
> By Pascal Pons and Matthieu Latapy
Posted in Plots | Tagged communities
By admin | Published: February 2, 2009
> By Massoud Seifi, Jean-Loup Guillaume and Matthieu Latapy Many real-world networks can be represented as large graphs. Computational manipulation of such large graphs is common, but current tools for graph visualization are limited to datasets of a few thousand nodes. These graphs contain sets of highly connected nodes that we call “communities”. Furthermore, these [...]
Posted in Plots | Also tagged visualization
By admin | Published: January 24, 2009
> By Thomas Aynaud and Jean-Loup Guillaume The modularity is widely used to evaluate the quality of a partition of a graph in communities. Each community contributes to the global modularity according to the formula below, where m is the number of links of the graph, e is the number of links inside a given [...]
Posted in Plots | Also tagged modularity
By admin | Published: November 14, 2008
> By Thomas Aynaud and Jean-Loup Guillaume When you try to detect communities in a complex network, you often build a hierarchical decomposition of the nodes. This decomposition is a tree (called a dendrogram). The leaves of the tree are the nodes, and each of its levels defines a partition: two nodes of the graph [...]
Posted in Plots | Also tagged social networks
By admin | Published: October 23, 2008
Vincent D. Blondel, Jean-Loup Guillaume, Renaud Lambiotte, Etienne Lefebvre
We propose a simple method to extract the community structure of large networks. Our method is a heuristic method that is based on modularity optimization. It is shown to outperform all other known community detection method in terms of computation time. Moreover, the quality of the communities detected is very good, as measured by the so-called modularity. This is shown first by identifying language communities in a Belgian mobile phone network of 2.6 million customers and by analyzing a web graph of 118 million nodes and more than one billion links. The accuracy of our algorithm is also verified on ad-hoc modular networks
Posted in Papers | Also tagged algorithm
By admin | Published: January 1, 2006
Pascal Pons and Matthieu Latapy
Dense subgraphs of sparse graphs (communities), which appear in most real-world complex networks, play an important role in many contexts. Computing them however is generally expensive. We propose here a measure of similarities between vertices based on random walks which has several important advantages: it captures well the community structure in a network, it can be computed efficiently, and it can be used in an agglomerative algorithm to compute efficiently the community structure of a network. We propose such an algorithm, called Walktrap, which runs in time O(mn²) and space O(n²) in the worst case, and in time O(n² log n) and space O(n²) in most real-world cases (n and m are respectively the number of vertices and edges in the input graph). Extensive comparison tests show that our algorithm surpasses previously proposed ones concerning the quality of the obtained community structures and that it stands among the best ones concerning the running time.
Posted in Papers | Also tagged random walks
