|
2016-present
-
Ricci curvatures in random clustering graphs, preprint,
(with M. Rawson, Z. Shen, N. Sieger and M. Xu).
-
Subgraph counts in
random clustering graphs,
Proceeding of the 19th Workshop on Algorithms and Models for the Web Graph (WAW 2024),
Lecture Notes in Computer Science 14671, Springer, 2024,
pp. 1-16,
(with Nick Sieger).
-
Quasi-random influences of Boolean functions
, Electronic Journal of Combinatorics, Volume 31, Issue 2, (2024), P2.52, 42 pages,
(with Nick Sieger).
-
A random graph model for clustering graphs
,
Proceeding of the 18th Workshop on Algorithms and Models for the Web Graph (WAW 2023),
Lecture Notes in Computer Science 13894, Springer, 2023,
pp. 112-126,
(with Nick Sieger).
-
The maximum relaxation time of a random walk
,
Advances in Applied Math., 101, (2018), 1--14,
(with S. G. Aksoy, M. Tait and J. Tobin)
-
Extreme values of the stationary distribution of random walks on directed graphs
,
Advance in Applied Math., 81, (2016), 128--155,
(with Sinan Aksoy and Xing Peng).
-
Decomposition of random graphs into complete bipartite graphs , SIAM J. Discrete Math., 30, no. 1, (2016), 296--310,
(with X. Peng).
2011-2015
-
A note on an alternating upper bound for random walks on semigroups
,
Discrete Applied Mathematics,
176 (2014), 24--29,
(with J. Hughes).
-
From quasirandom graphs to graph limits and graphlets
,
Advances in Applied Math. 56 (2014),
135--174.
-
Braess's paradox in expanders
,
Random Structures and Algorithms, 41 (2012), 451--468,
(with S. J. Young and W. Zhao).
-
Diameter
of random spanning trees in a given graph ,
Journal of Graph Theory,
69, (2012), 223--240,
(with P. Horn and L. Lu).
-
On the spectra of general random graphs,
Electronic Journal of Combinatorics, 18(1),
(2011), P215, 14 pages,
(with M. Radcliffe).
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).
-
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.
-
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.
-
Concentration
inequalities and martingale inequalities --- a survey,
Internet Math.,
3 (2006-2007), 79--127,
(with L. Lu).
-
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.
2001-2005
Back to top
-
Laplacians
and the Cheeger inequality for
directed graphs,
Annals of Combinatorics, 9 (2005), 1--19.
-
De Bruijn cycles for covering codes,
Random Structures and Algorithms, 25, (2004), 421--431,
(with J. Cooper).
-
Coupling online and offline analyses for random power law graphs,
Internet Mathematics, 1 (2004), 409--461,
(with Lincoln Lu).
- 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).
-
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).
-
Sparse quasi-random graphs,
abstract,
Combinatorica 22 (2002), 217--244,
(with Ronald Graham)
-
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).
-
Combinatorics for the East model,
abstract,
Advances in Applied Math. 27 (2001), 192--206,
(with Persi Diaconis and Ronald Graham).
-
The diameter of sparse random graphs,
abstract,
Advances in Applied Math. 26 (2001), 257--279,
(with Linyuan Lu).
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.
-
Logarithmic Sobolev techniques for random walks on graphs,
Emerging Applications of Number Theory, IMA Volumes in Math. and its Applications
109 (eds. D. A. Hejhal et. al.), 175--186, Springer, 1999.
-
Stratified random walks on an n-cube,
Random Structures and Algorithms 11 (1997), 199--222,
(with R.L. Graham).
-
Random walks on generating sets of groups,
Electronic Journal of Combinatorics 4 no. 2, (1997) #R7, 14 pp,
(with R. L. Graham).
-
On sampling with Markov chains,
Random Structures and Algorithms 9 (1996) 55--77.
(with R. L. Graham and S. -T. Yau).
1991-1995
Back to top
-
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.
-
Communication complexity and quasi-randomness,
SIAM J. Discrete Math. 6 (1993), 110--123,
(with Prasad Tetali)
-
On hypergraphs having evenly distributed subhypergraphs,
Disc. Math. 111 (1993), 125--129,
(with Ron Graham).
-
Cohomological aspects of hypergraphs,
Trans. Amer. Math. Soc. 334 (1992), 365--388,
(with R. L. Graham).
-
Maximum cuts and quasirandom graphs,
in Random Graphs, John Wiley and Sons (1992), 23--33,
(with R.L. Graham).
-
Quasi-random set systems,
J. Amer. Math. Soc. 4 (1991), 151--196,
(with R. L. Graham).
-
Constructing random-like graphs,
Probabilistic Combinatorics and Its Applications, (B. Bollobas ed.), Amer. Math. Soc., Providence, (1991), 21--55.
-
Quasi-random tournaments,
J. of Graph Theory 15 (1991), 173--198,
(with R.L. Graham).
-
Regularity lemmas for hypergraphs and quasi-randomness,
Random Structures and Algorithms 2 (1991), 241--252.
1986-1990
Back to top
-
Quasi-random classes of hypergraphs,
Random Structures and Algorithms 1 (1990), 363--382.
Corrigendum.
-
On graphs not containing prescribed induced subgraphs,
in A Tribute to Paul Erdos, Cambridge University Press (1990), 111--120,
(with R.L. Graham).
-
Quasi-random graphs,
a short
version appeared in Proc. Natl. Acad. Sci. USA, 85 (1988), 969--970,
a long
version
appeared in Combinatorica 9 (1989), 345--362,
(with R. L. Graham and R. M. Wilson).
-
Quasi-random hypergraphs,
Proc. Natl. Acad. Sci. USA 86 (1989), 8175--8177,
Long
version appeared in Random Structures
and Algorithms 1 (1990), 105--124,
(with R.L. Graham).
-
Explicit construction of linear sized tolerant networks,
Discrete Math. 72 (1988), 15--19,
(with N. Alon).
-
The diameter of a cycle plus a random matching,
SIAM J. on Discrete Math. 1 (1988), 328--333.
(with B. Bollobás)
-
Random walks arising in random number generation,
Ann. Probab. 15 (1987), no. 3, 1148--1165,
(with P. Diaconis and R.L. Graham).
1981-1985
Back to top
1975-1980
Back to top
1973-1975
Back to top
|