Finding, counting and/or listing triangles (three vertices with three edges) in massive graphs are natural fundamental problems, which received recently much attention because of their importance in complex network analysis. We provide here a detailed survey of proposed main-memory solutions to these problems, in an uni?ed way. We note that previous authors paid surprisingly little attention to space complexity of main-memory solutions, despite its both fundamental and practical interest. We therefore detail space complexities of known algorithms and discuss their implications. We also present new algorithms which are time optimal for triangle listing and beats previous algorithms concerning space needs. They have the additional advantage of performing better on power-law graphs, which we also detail. We ?nally show with an experimental study that these two algorithms perform very well in practice, allowing to handle cases which were previously out of reach.

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.