Fan Chung Graham

	Papers of Fan Chung - (back to the full list)	[ Erdös \| eigen \| graphs \| extremal \| random \| powerlaw ] [ algorithm \| geometry \| number theory \| Internet \| surveys ] Keyword search:

2016-present,

2011-2015,

2006-2010,

2001-2005,

1996-2000,

1991-1995,

1986-90,

1981-85,

1976-80,

1973-75

2016-present

2011-2015

From quasirandom graphs to graph limits and graphlets ,
Advances in Applied Math. 56 (2014), 135--174.

Solving linear systems with boundary conditions using heat kernel pagerank
WAW 2013, LNCS 8305, 203--219, (with Olivia Simpson). The journal version appeared in Internet Mathematics, 11 (2015), 449-471.

A local clustering algorithm for connection graphs ,
WAW 2013, LNCS 8305, 203--219, (with Mark Kempton). The journal version appeared in Internet Math., 11 (2015), 333-351.

Spectral clustering of graphs with general degrees in the extended planted partition model ,
COLT 2012, Journal of Machine Learning Research, (2012), 1--23, (with K. Chaudhuri and A. Tsiatas).

Multi-commodity allocation for dynamic demands using PageRank vectors ,
WAW2012, LNCS 7323 (2012), 138--152, (with P. Horn and J. Hughes). The journal version appeared in Internet Mathematics, 10 (2014), 49--65.

Braess's paradox in expanders ,
Random Structures and Algorithms, 41 (2012), 451--468, (with S. J. Young and W. Zhao).

Hypergraph coloring games and voter models ,
WAW2012, LNCS 7323 (2012), 1--16, (with Alex Tsiatas). The journal version appeared in Internet Mathematics, 10 (2014), 66--86.

Edge flipping in graphs,
Advances in Applied Mathematics, 48 (2012) 37--63, (with Ron Graham).

Diameter of random spanning trees in a given graph ,
Journal of Graph Theory, 69, (2012), 223--240, (with P. Horn and L. Lu).

Dirichlet PageRank and trust-based ranking algorithms,
WAW 2011, LNCS 6732, (2011), 103--114, (with A. Tsiatas and Wensong Xu).
The journal version, Dirichlet PageRank and ranking algorithms based on trust and distrust, appeared in Internet Mathematics, 9, (2013), 113--134.

2006-2010 Back to top

Graph Theory in the information age ,
Notices of AMS, 57, no. 6, July 2010, 726--732.
This article was translated into Chinese and appeared in Mathematical Advances in Translation, 3, 2010, 207--213.
PageRank and random walks on graphs ,
Fete of Combinatorics and Computer Science, (G. O. H. Katona, A. Schrijver and T. Szonyi, Eds.), Springer, Berlin, (2010), 43--62, (with Wenbo Zhao).
Small spectral gap in the combinatorial Laplacian implies Hamiltonian,

Annals of Combinatorics, 13, (2010), 403--412, (with S. Butler).
Finding and visualizing graph clusters using PageRank optimization,
WAW 2010, LNCS 6516, (2010), 86--97, (with A. Tsiatas).
The journal version appeared in Internet Mathematics, 8 (2012), 46--72, (with A. Tsiatas).
Braess's paradox in large sparse graphs, WINE 2010, LNCS 6484, 194--208, (with Stephen J. Young).
A sharp PageRank algorithm with applications to edge ranking and graph sparsification
WAW 2010, LNCS 6516, 2--14, (with Wenbo Zhao).
PageRank as a discrete Green's function,
Geometry and Analysis, I, ALM 17, (2010), 285--302.
A local graph partitioning algorithm using heat kernel pagerank,
WAW 2009, LNCS 5427, (2009), 62-75.
Distributing antidote using PageRank vectors ,
Internet Mathematics, 6, (2009), 237--254, (with Paul Horn and Alexander Tsiatas).
The giant component in a random subgraph of a given graph ,
Proceedings of WAW2009, Lecture Notes in Computer Science 5427, 38--49, (with P. Horn and L. Lu).
A whirlwind tour of random graphs ,
a survey article in Encyclopedia on Complex Systems, Springer, 2008.
A network color game ,
WINE 2008, Lecture Notes in Computer Science, Volume 5385 (2008), 522--530, (with K. Chaudhuri and M. S. Jamall).
Quasi-random graphs with given degree sequences,
Random Structures and Algorithms, 12 (2008), 1--19, (with R. L. Graham).
Four Cheeger-type inequalities for graph partitioning algorithms ,
Proceedings of ICCM, II, (2007), 751--772.
The heat kernel as the pagerank of a graph ,
PNAS, 105 (50), (2007), 19735--19740.
Local partitioning for directed graphs using PageRank ,
WAW2007, 166--178, (with R. Andersen and Kevin Lang).
The full paper is in Internet Mathematics, 5 (2008), 3--22.
The spectral gap of a random subgraph of a graph,
the extended abstract appeared in Proceedings of WAW2006, LNCS 4937 and the complete version is in Internet Math, 4 (2007), 225-244,
(with Paul Horn).
Detecting sharp drops in PageRank and a simplified local partitioning algorithm
Theory and Applications of Models of Computation, Proceedings of TAMC 2007, LNCS 4484, Springer, (2007), 1--12, (with R. Andersen).
Local graph partitioning using pagerank vectors,
FOCS 2006, 475-486, (with R. Andersen and K. Lang). The full paper version, Using pagerank vectors to locally partition a graph appeared in Internet Mathematics, 4 (2007), 35--64.
Random walks and local cuts in graphs,
Linear Algebra and its Applications, 423 (2007), 22--32.

Oblivious and adaptive strategies for the majority and plurality problems,
Algorithmica, 48 (2007), 147--157, (with R. Graham, Jia Mao and Andrew Yao)

Concentration inequalities and martingale inequalities --- a survey,
Internet Math., 3 (2006-2007), 79--127, (with L. Lu).

Maximizing data locality in distributed systems,
Journal of Computer System Sciences, 72 (December 2006), 1309-1316, (with Ronald Graham, Ranjita Bhagwan, Stefan Savage and Geoffrey M. Voelker).

The volume of the giant component of a random graph with given expected degrees,
SIAM J. Discrete Math. 20 (2006), no. 2, 395--411, (with L. Lu).

A brief overview of network algorithms,
J. of Computer and System Sciences 72 (2006), no. 3, 420--424.

Complex Graphs and Networks,
CBMS Number 107, AMS Publications, 2006, vii+264pp., (with L. Lu)

2001-2005 Back to top

Laplacians and the Cheeger inequality for directed graphs,
Annals of Combinatorics, 9 (2005), 1--19.

Oblivious strategies for the majority and plurality problems,
Computing and Combinatorics, Lecture Notes in Computer Science, Springer, Berlin (2005), 329--338,
(with R. Graham, Jia Mao and Andrew Yao).
The journal version appeared in Algorithmica 48 (2007), 147--157.

A spectral Turán theorem,
Combinatorics, Probability and Computing 14 (2005), 755--767.

Drawing power law graphs,
Proceedings Graph Drawing, New York, 2004, 12--17, (with Reid Andersen, L. Lu).
Paper version, Drawing power law graphs using a local/global decomposition, appeared in Algorithmica 47 (2007), 379--397.

Analyzing the small world phenomenon using a hybrid model with local network flow,
WAW 2004, Rome, Italy, Lecture Notes in Computer Science, 3234, Springer, 2004, 19--30,
a long version appeared as Modeling the small-world phenomenon with local network flow,
Internet Mathematics 2 (2006), no. 3, 359--385,
(with Reid Andersen, L. Lu).

Guessing secrets with inner product questions,
Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms, (2002), 247--253,
long version appeared in Internet Math., 1 (2004), no. 2, 177--192,
(with R.L. Graham and Linyuan Lu).

Parallelism versus Memory Allocation in Pipelined Router Forwarding Engines,
SPAA'04, Barcelona, Spain, (2004), 103--111,
(with Ronald Graham and George Varghese).

Coupling online and offline analyses for random power law graphs,
Internet Mathematics, 1 (2004), 409--461,
(with Lincoln Lu).

Discrete isoperimetric inequalities,
Surveys in Differential Geometry IX, International Press, (2004), 53--82.

On disjoint path pairs with wavelength continuity constraint in WDM networks,
INFOCOM, 2004,
(with Reid Andersen, Arunabha Sen and Guoliang Xue).

The small world phenomenon in hybrid power law graphs,
Complex Networks, (Eds. E. Ben-Naim et. al.), Springer-Verlag, (2004), 89--104,
(with Lincoln Lu).

Generalizations of Polya's urn problem,
Annals of Combinatorics 7 (2003), 141--153,
(with Shirin Handjani and Doug Jungreis).

Finding Favorites,
Electronic Colloquium on Computational Complexity, Report No. 78 (2003),
(with Ron Graham, Jia Mao and Andrew Yao).
Eigenvalues of random power law graphs,
Annals of Combinatorics 7 (2003), 21--33,
(with Lincoln Lu and Van Vu).

The spectra of random graphs with given expected degrees,
short version, Proceedings of National Academy of Sciences 100, no. 11, (2003), 6313--6318,
long version (with full proofs) Internet Mathematics 1 (2004), 257--275,
(with Lincoln Lu and Van Vu).

Duplication models for biological networks,
Journal of Computational Biology 10, no. 5, (2003), 677--688,
(with Lincoln Lu, Gregory Dewey, David J. Galas).

The average distances in random graphs with given expected degrees, abstract,
paper (short version), Proc. National Academy of Sciences 99, no. 25, (December, 2002), 15879--15882,
paper (long version) , Internet Mathematics 1 (2003), 91--113,
(with L. Lu).

Spectral Partitioning with Indefinite Kernels using the Nyström Extension,
European Conference on Computer Vision, 2002, III, 531--542.
Paper version: Spectral grouping using the Nyström method,
IEEE Transactions on Pattern Analysis and Machine Intelligence 26, No. 2, (2004), 214--225,
(with Charless Fowlkes, Serge Belongie, and Jitendra Malik).

Connected components in random graphs with given expected degree sequences, abstract,
Annals of Combinatorics 6 (2002), 125-145,
(with L. Lu).

Random evolution of massive graphs, abstract,
Handbook of Massive Data Sets, (Eds. James Abello et al.), Kluwer Academic Publishers, (2002), 97--122,
extended abstract appeared in FOCS 2001, 510--519,
(with W. Aiello and L. Lu).

Guessing secrets, abstract,
Electronic Journal of Combinatorics 8 (2001), R13, 25 pp,
extended abstract appeared in Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (Washington, DC, 2001), SIAM, Philadelphia, 723--726, (with Ron Graham and Tom Leighton). also, SODA'01, 723--726,
(with Ronald Graham and F. Tom Leighton).

Distance realization problems with applications to Internet tomography,
J. Computer and System Sciences 63 No. 3, (November 2001), 432--448,
(with Mark Garrett, Ronald Graham and David Shallcross).

The diameter of sparse random graphs, abstract,
Advances in Applied Math. 26 (2001), 257--279,
(with Linyuan Lu).

Dynamic location problems with limited look-ahead,
Theoretical Computer Science 261 (2001), 213--226,
(with Ron Graham).

Augmented ring networks,
IEEE Transactions on Parallel and Distributed Systems 12 (2001), 598--609,
(with W. Aiello, S. N. Bhatt, A. L. Rosenberg and R. K. Sitaraman).

1996-2000 Back to top

A random graph model for massive graphs, abstract,
Proceedings of the Thirtysecond Annual ACM Symposium on Theory of Computing (2000), 171--180,
(with Bill Aiello and Linyuan Lu).
The complete paper version has a different title A random graph model for power law graphs,
Experimental Math. 10 (2001), 53--66.

Optical wavelength routing, translation, and packet/cell switched networks,
Journal of Lightwave Technology 14, Issue 3, March 1996, 336--343,
(with Krishna Bala and Charles A. Brackett).
Maximum subsets of $(0,1]$ with no solutions to $x+y=kz$,
Electronic Journal of Combinatorics 3 (1996) R1, 23 pp,
(with John L. Goldwasser).

1991-1995 Back to top

Routing permutations on graphs via matchings,
SIAM J. Discrete Math. 7 (1994) 513--530,
(with Noga Alon and R. L. Graham).

A report on reliable software and communication,
Bellcore Internal Memorandom 1992. Paper version titled "Reliable software and communication: An overview", IEEE J. Selected Areas Comm. 12, no. 1 (1994), 23--32.

Graphs with small diameter after edge deletion,
Discrete Applied Math. 37/38 (1992), 73--94.

1986-1990 Back to top

The diameter of a cycle plus a random matching,
SIAM J. on Discrete Math. 1 (1988), 328--333.
(with B. Bollobás)

Diameters of graphs: old problems and new results,
Congressus Numerantium 60 (1987), 295--317.

1981-1985 Back to top

1975-1980 Back to top

1973-1975 Back to top

<< Back to Research Home

¨ 2000-2006 Fan Chung Graham