Fan Chung

Fan Chung

Auto-generated profile, based on publicly available information

Fan Chung

University of California, San Diego

Research Focus & Metrics

Academic Career Length

26Years (2001-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
4 December 2002 in Proceedings of the National Academy of Sciences
Verified
Journal Article
Closed access
FCFan Chung
Fan Chung
LLLinyuan Lu
Linyuan Lu
Random graph theory is used to examine the “small-world phenomenon”; any two strangers are connected through a short chain of mutual acquaintances. We will show that for certain families of random graphs with given expected degrees the average distance is almost surely of order logn/logd̃,whered̃is the weighted average of the sum of squares of the expected degrees. Of particular interest are power law random graphs in which the number of vertices of degreekis proportional to1/kβfor some fixed exponent β. For the case of β > 3, we prove that the average distance of the power law graphs is almost surely of order logn/logd̃.However, many Internet, social, and citation networks are power law graphs with exponents in the range 2 < β < 3 for which the power law random graphs have average distance almost surely of order log logn,but have diameter of order logn(provided having some mild constraints for the average distance and maximum degree). In particular, these graphs contain a dense subgraph, which we call the core, havingnc/log lognvertices. Almost all vertices are within distance log lognof the core although there are vertices at distance lognfrom the core.

1 April 2005 in Annals of Combinatorics
Verified
Journal Article
Closed access
PDF file
FCFan Chung
Fan Chung

12 May 2003 in Proceedings of the National Academy of Sciences
Verified
Journal Article
Closed access
FCFan Chung
Fan Chung
LLLinyuan Lu
Linyuan Lu
VVVan Vu
Van Vu
In the study of the spectra of power-law graphs, there are basically two competing approaches. One is to prove analogues of Wigner's semicircle law, whereas the other predicts that the eigenvalues follow a power-law distribution. Although the semicircle law and the power law have nothing in common, we will show that both approaches are essentially correct if one considers the appropriate matrices. We will prove that (under certain mild conditions) the eigenvalues of the (normalized) Laplacian of a random power-law graph follow the semicircle law, whereas the spectrum of the adjacency matrix of a power-law graph obeys the power law. Our results are based on the analysis of random graphs with given expected degrees and their relations to several key invariants. Of interest are a number of (new) values for the exponent β, where phase transitions for eigenvalue distributions occur. The spectrum distributions have direct implications to numerous graph algorithms such as, for example, randomized algorithms that involve rapidly mixing Markov chains.

1 January 2001 in Experimental Mathematics
Verified
Journal Article
Closed access
WAWilliam Aiello
William Aiello
FCFan Chung
Fan Chung
LLLinyuan Lu
Linyuan Lu
We propose a random graph model which is a special case of sparserandom graphs with given degree sequences which satisfy a power law. This model involves only a small number of paramo eters, called logsize and log-log growth rate. These parameters capture some universal characteristics of massive graphs. From these parameters, various properties of the graph can be derived. For example, for certai n ranges of the parameters, we wi II compute the expected distribution of the sizes of the connected components which almost surely occur with high probability. We illustrate the consistency of our model with the behavior of some massive graphs derived from data in telecommunications. We also discuss the threshold function, the giant component, and the evolution of random graphs in this model.

11 December 2007 in Proceedings of the National Academy of Sciences
Verified
Journal Article
Closed access
FCFan Chung
Fan Chung
The concept of pagerank was first started as a way for determining the ranking of Web pages by Web search engines. Based on relations in interconnected networks, pagerank has become a major tool for addressing fundamental problems arising in general graphs, especially for large information networks with hundreds of thousands of nodes. A notable notion of pagerank, introduced by Brin and Page and denoted by PageRank, is based on random walks as a geometric sum. In this paper, we consider a notion of pagerank that is based on the (discrete) heat kernel and can be expressed as an exponential sum of random walks. The heat kernel satisfies the heat equation and can be used to analyze many useful properties of random walks in a graph. A local Cheeger inequality is established, which implies that, by focusing on cuts determined by linear orderings of vertices using the heat kernel pageranks, the resulting partition is within a quadratic factor of the optimum. This is true, even if we restrict the volume of the small part separated by the cut to be close to some specified target value. This leads to a graph partitioning algorithm for which the running time is proportional to the size of the targeted volume (instead of the size of the whole graph).

1 July 2003 in Annals of Combinatorics
Verified
Journal Article
Closed access
PDF file
FCFan Chung
Fan Chung
SHShirin Handjani
Shirin Handjani
DJDoug Jungreis
Doug Jungreis