Title: Probabilistic Methods for Complex Graphs
Speaker: Dr. Lu Linyuan, University of South Carolina
Time: 13:30pm—14:30pm, December 26th, 2011 (Monday)
Place: Room 440, 4th Floor, ICT, CAS
Abstract:
It was observed that many real-world networks such as the Internet, social networks, biological networks, and Collaboration graphs have the so-called power law degree distributions. A graph is called a power law graph if the fraction of vertices with degree k is approximately proportional to k^{-b} for some constant b. The classical Erdos and Renyi random graph model G(n,p) is not suitable for modeling these power law graphs. Many random graphs models are developed. Among these models, Chung and Lu directly generalize G(n,p) into ``random graphs with given expected degree sequences''. They determined the size and volume of the giant component, the average distance and the diameter, and the spectra. Some theoretic results will be compared to real data.
(Joint work with Fan Chung Graham.)
Bio:
Professor Linyuan Lu is currently an associate professor at the University of South Carolina. His research interests includes Large information networks, probabilistic methods, spectral graph theory, random graphs, extremal problems on hypergraphs and posets, algorithms, and graph theory. Dr. Lu received his Ph.D. in Mathematics from the University of California, San Diego in 2002. Dr. Lu has published 40+ papers and a book 'Complex graphs and networks' (coauthored with Fan Chung Graham). He won a $100 prize by solving a twenty-year-old Erdos problem. He is the managing editor of Journal of Combinatorics.

Center for Advanced Computing Research, ICT
December, 2011