The diameter of a graph is among its most basic parameters. Since a few years, it moreover became a key issue to compute it for massive graphs in the context of complex network analysis. However, known algorithms, including the ones producing approximate values, have too high a time and/or space complexity to be used in such cases. We propose here a new approach relying on very simple and fast algorithms that compute (upper and lower) bounds for the diameter. We show empirically that, on various real-world cases representative of complex networks studied in the literature, the obtained bounds are very tight (and even equal in some cases). This leads to rigorous and very accurate estimations of the actual diameter in cases which were previously untractable in practice.

In contrast with most internet topology measurement research, our concern here is not to obtain a map as complete and precise as possible of the whole internet. Instead, we claim that each machine's view of this topology, which we call ego-centered view, is an object worth of study in itself. We design and implement an ego-centered measurement tool, and perform radar-like measurements consisting of repeated measurements of such views of the internet topology. We conduct long-term (several weeks) and high-speed (one round every few minutes) measurements of this kind from more than one hundred monitors, and we provide the obtained data. We also show that these data may be used to detect events in the dynamics of internet topology.

During the last decade, the study of large scale complex networks has attracted asubstantial amount of attention and works from several domains: sociology, biology,computer science, epidemiology. Most of such complex networks are inherently dy-namic, with new vertices and links appearing while some old ones disappear. Untilrecently, the dynamic of these networks was less studied and there is a strong needfor dynamic network models in order to sustain protocol performance evaluationsand fundamental analyzes in all the research domains listed above.We propose in this paper a novel framework for the study of dynamic mobilitynetworks. We address the characterization of dynamics by proposing an in-depthdescription and analysis of two real-world data sets. We show in particular thatlinks creation and deletion processes are independent of other graph properties andthat such networks exhibit a large number of possible con¯gurations, from sparse todense. From those observations, we propose simple yet very accurate models thatallow to generate random mobility graphs with similar temporal behavior as theone observed in experimental data.

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