Home Conference Schedule
	SCHEDULE: NOV 11-17, 2006 Parallel Massive Scale-Free Graph Generators Session: Poster Reception Event Type: Poster Time: 5:15pm - 7:15pm Author(s): Andy Yoo, Keith Henderson Location: Ballroom Corridor Abstract: The lack of publicly available large scale-free graphs forces researchers studying massive scale-free graphs to rely on synthetically generated graphs in testing and evaluating their algorithms. This requires a graph generator that can scale to the graphs with potentially tens and hundreds of billions of vertices and edges. We have developed two such scalable parallel graph generators in this research. The parallel Barabasi-Albert method iteratively builds scale-free graphs using two-phase preferential attachment technique in a bottom-up fashion. The parallel Kronecker method, on the other hand, constructs a graph recursively in a top-down fashion from a given seed graph using the Kronecker matrix multiplication. We show that both graph generators generate massive graphs at a very high rate. It is also shown that graphs generated by these methods have all the common properties of the real scale-free graphs such as power-law degree distribution and small-worldness. Chair/Author Details: Andy Yoo Lawrence Livermore National Laboratory Keith Henderson Lawrence Livermore National Laboratory
	Home | About | Contact Us | Registration | Sitemap