Academic
Publications
Patterns on the Connected Components of Terabyte-Scale Graphs

Patterns on the Connected Components of Terabyte-Scale Graphs,10.1109/ICDM.2010.121,U. Kang,Mary McGlohon,Leman Akoglu,Christos Faloutsos

Patterns on the Connected Components of Terabyte-Scale Graphs   (Citations: 2)
BibTex | RIS | RefWorks Download
How do connected components evolve? What are the regularities that govern the dynamic growth process and the static snapshot of the connected components? In this work, we study patterns in connected components of large, real-world graphs. First, we study one of the largest static Web graphs with billions of nodes and edges and analyze the regularities among the connected components using GFD(Graph Fractal Dimension) as our main tool. Second, we study several time evolving graphs and find dynamic patterns and rules that govern the dynamics of connected components. We analyze the growth rates of top connected components and study their relation over time. We also study the probability that a newcomer absorbs to disconnected components as a function of the current portion of the disconnected components and the degree of the newcomer. Finally, we propose a generative model that explains both the dynamic growth process and the static regularities of connected components.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: