
2016present
20112015
 Distributed algorithms for finding local clusters using heat kernel pagerank, WAW, 2015,
LNCS 9479, Springer, 177189,
(with O. Simpson).

A brief survey of PageRank algorithms,
IEEE Transactions on Network Science and Engineering, 1, No. 1, (2015), 3842.

Complex Networks, a chapter in Handbook of Graph Theory, (eds. J. L. Gross et. al), 14561476, CRC Press, 2014,
(with A. Bonato).

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

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

A local clustering algorithm for connection graphs
,
WAW 2013, LNCS 8305, 203219,
(with Mark Kempton).
The journal version appeared in Internet Math., 11 (2015), 333351.

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

Ranking and sparsifying a connection graph,
WAW 2012,
LNCS 7323 (2012), 6677,
(with M. Kempton and W. Zhao).
The journal version appeared in Internet Mathematics, 10 (2014), 87115.

Multicommodity allocation for dynamic demands using PageRank vectors
,
WAW2012,
LNCS 7323 (2012), 138152,
(with P. Horn and J. Hughes).
The journal version appeared in Internet Mathematics, 10 (2014), 4965.

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

Hypergraph coloring games and voter models
,
WAW2012, LNCS 7323 (2012), 116,
(with Alex Tsiatas).
The
journal version appeared in Internet Mathematics, 10 (2014), 6686.

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

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

Dirichlet PageRank and trustbased ranking algorithms,
WAW 2011, LNCS 6732, (2011), 103114,
(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), 113134.
20062010
Back to top

Graph Theory in the information age
,
Notices of AMS, 57, no. 6, July 2010, 726732.
This article was translated into Chinese and appeared in
Mathematical Advances in Translation, 3, 2010, 207213.

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), 4362,
(with Wenbo Zhao).

Small
spectral gap in the combinatorial Laplacian implies Hamiltonian,
Annals of Combinatorics, 13, (2010), 403412,
(with S. Butler).

Finding and visualizing graph clusters using PageRank optimization,
WAW 2010, LNCS 6516, (2010), 8697,
(with A. Tsiatas).
The journal version appeared in Internet Mathematics, 8 (2012), 4672,
(with A. Tsiatas).

Braess's paradox in large sparse graphs,
WINE 2010, LNCS 6484, 194208,
(with Stephen J. Young).

A sharp PageRank algorithm with applications to edge ranking and graph sparsification
WAW 2010, LNCS 6516, 214,
(with Wenbo Zhao).

PageRank
as a discrete Green's function,
Geometry and Analysis, I, ALM 17, (2010), 285302.

A local graph
partitioning algorithm using heat kernel pagerank,
WAW 2009,
LNCS 5427, (2009), 6275.

Distributing antidote using PageRank vectors
,
Internet Mathematics, 6, (2009), 237254,
(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, 3849,
(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), 522530,
(with K. Chaudhuri and M. S. Jamall).

Quasirandom graphs with
given degree sequences,
Random Structures and Algorithms, 12 (2008), 119,
(with R. L. Graham).

Four
Cheegertype inequalities for graph
partitioning algorithms
,
Proceedings of ICCM, II, (2007), 751772.

The heat kernel as the pagerank of a graph
,
PNAS, 105 (50), (2007), 1973519740.

Local partitioning for directed graphs using PageRank
,
WAW2007, 166178,
(with R. Andersen and Kevin Lang).
The full paper is in Internet Mathematics, 5 (2008), 322.

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), 225244,
(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), 112,
(with R. Andersen).

Local
graph partitioning using pagerank vectors,
FOCS 2006, 475486,
(with R. Andersen and K. Lang).
The full paper version,
Using pagerank vectors to locally partition a graph appeared in Internet Mathematics, 4 (2007), 3564.

Random walks and local cuts
in graphs,
Linear Algebra and its Applications, 423 (2007), 2232.
 Oblivious and adaptive strategies for the majority and plurality problems,
Algorithmica, 48 (2007), 147157,
(with R. Graham, Jia Mao and Andrew Yao)

Concentration
inequalities and martingale inequalities  a survey,
Internet Math.,
3 (20062007), 79127,
(with L. Lu).

Maximizing data locality in distributed systems,
Journal of Computer System Sciences, 72 (December 2006),
13091316,
(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, 395411,
(with L. Lu).

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

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

Laplacians
and the Cheeger inequality for
directed graphs,
Annals of Combinatorics, 9 (2005), 119.
 Oblivious strategies for the majority and plurality problems,
Computing and Combinatorics, Lecture Notes in Computer Science, Springer, Berlin (2005), 329338,
(with R. Graham, Jia Mao and Andrew Yao).
The journal version appeared in Algorithmica 48 (2007), 147157.

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

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

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, 1930,
a long version appeared as
Modeling the smallworld phenomenon with local network flow,
Internet Mathematics 2 (2006), no. 3, 359385,
(with Reid Andersen, L. Lu).
 Guessing secrets with inner product questions,
Proceedings of the 13th ACMSIAM Symposium on Discrete Algorithms, (2002), 247253,
long version appeared in Internet Math., 1 (2004), no. 2, 177192,
(with R.L. Graham and Linyuan Lu).

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

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

Discrete isoperimetric inequalities,
Surveys in Differential Geometry IX, International Press, (2004), 5382.

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. BenNaim et. al.), SpringerVerlag, (2004), 89104,
(with Lincoln Lu).

Generalizations of Polya's urn problem,
Annals of Combinatorics 7 (2003), 141153,
(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), 2133,
(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), 63136318,
long version
(with full proofs) Internet Mathematics 1 (2004), 257275,
(with Lincoln Lu and Van Vu).

Duplication models for biological networks,
Journal of Computational Biology 10, no. 5, (2003), 677688,
(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), 1587915882,
paper (long version)
,
Internet Mathematics 1 (2003), 91113,
(with L. Lu).

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

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

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

On sparse sets hitting linear forms,
abstract,
Number Theory for the Millennium I,
(Eds. M. A. Bennett et al.), AK Peters, Natick, Massachusetts, (2002), 257272.
(with Paul Erdös and Ronald Graham)

Guessing secrets,
abstract,
Electronic Journal of Combinatorics 8 (2001), R13, 25 pp,
extended
abstract appeared in
Proceedings of the Twelfth Annual ACMSIAM Symposium on Discrete Algorithms
(Washington, DC, 2001), SIAM, Philadelphia, 723726,
(with Ron Graham and Tom Leighton).
also, SODA'01, 723726,
(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), 432448,
(with Mark Garrett, Ronald Graham and David Shallcross).

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

Dynamic location problems with limited lookahead,
Theoretical Computer Science 261 (2001), 213226,
(with Ron Graham).

Augmented ring networks,
IEEE Transactions on Parallel and Distributed Systems 12 (2001), 598609,
(with W. Aiello, S. N. Bhatt, A. L. Rosenberg and R. K. Sitaraman).
19962000
Back to top

A random graph model for massive graphs,
abstract,
Proceedings of the
Thirtysecond Annual ACM Symposium on Theory of Computing
(2000),
171180,
(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), 5366.

On optimal strategies for cyclestealing in networks of workstations,
IEEE Trans. on Computers 46 (1997), 545557,
(with S. Bhatt, F. T. Leighton, and A. L. Rosenberg).

Optical wavelength routing, translation, and packet/cell switched networks,
Journal of Lightwave Technology 14, Issue 3, March 1996, 336343,
(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).

Optimal emulations by butterflylike networks,
JACM 43 (1996), 293330,
(with S. Bhatt, JiaWei Hong, F. T. Leighton, Bojana Obrenic, A. L. Rosenberg and E.J. Schwabe).
19911995
Back to top

Routing permutations on graphs via matchings,
SIAM J. Discrete Math. 7 (1994) 513530,
(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), 2332.

Tolerating faults in synchronization networks,
Parallel processing: CONPAR 92VAPP V (Lyon, 1992), Lecture Notes in
Comput. Sci., 634, Springer, Berlin, 1992, 112,
(with S. N. Bhatt, F. T. Leighton and A. L. Rosenberg).

Graphs with small diameter after edge deletion,
Discrete Applied Math. 37/38 (1992), 7394.
19861990
Back to top

Optimal simulations by butterfly networks,
Proc. of the Twentieth Annual ACM Symposium on Theory of Computing, (1988), 192204,
(with S. N. Bhatt, JiaWei Hong, F. T. Leighton and A. L. Rosenberg).

Explicit construction of linear sized tolerant networks,
Discrete Math. 72 (1988), 1519,
(with N. Alon).

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

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

The forwarding index of communication networks,
IEEE Trans. Inform. Theory 33 (1987), no. 2, 224232,
(with E.G. Coffman, Jr., M.I. Reiman, and B.E. Simon).

The relationship between switch capacity
and network capacity in packet switched networks,
Bell Laboratories Internal Memorandum, 1986,
(with R.R.Goldberg).
19811985
Back to top

Strongly connected orientations of mixed multigraphs,
Networks 15 (1985), no. 4, 477484, (with M.R. Garey and R.E. Tarjan).

Diameters of communication networks,
Mathematics of information processing (Louisville, Ky., 1984), 118, Proc. Sympos.
Appl. Math. 34 Amer. Math. Soc., Providence, RI, 1986.

Efficient realization techniques for network
flow patterns,
Bell System Tech. J. 60 (1981), no. 8, 17711786,
(with R. L. Graham and F. K. Hwang).
19751980
Back to top

On switching networks and block designs, II,
Bell System Tech. J. 59 (1980), 11651173.

On concentrators, superconcentrators, generalizers,
and nonblocking networks,
Bell System Tech. J. 58 (1979), 17651777.

The largest minimal rectilinear Steiner trees
for a set of n points enclosed in a rectangle with given perimeter,
Networks 9 (1979), 1936,
(with F. K. Hwang).

Zonebalanced networks and block designs,
Bell System Tech. J. 57 (1978), 29572971.

Optimal multistage switching networks,
IEEE Trans. on Communications COM26 (1978), 12821287.

An algebraic approach to switching networks,
Bell Laboratories Internal Memorandom, 1978.

A problem on blocking probabilities in connecting
networks,
Networks 7 (1977), 185192,
(with F. K. Hwang). 
On blocking probabilities for switching networks,
Bell System Tech. J. 56 (1977), 14311446,
(with F. K. Hwang).

On switching networks and block designs,
Conf. Record of the 10th Asilomar conf. on Circuits System and Computers
(1976), 212218.
19731975
Back to top
