Random graphs and web graph models
Equipartitions of graphs.
D. Eppstein,
J. Feigenbaum, and
C.L. Li.
Discrete Mathematics 91 (3): 239–248, 1991.
Considers partitions of the vertices of a graph into equal subsets, with few pairs of subsets connected by edges. (Equivalently we view the graph as a subgraph of a product in which one factor is sparse.) A random graph construction shows that such a factorization does not always exist.
The distribution of cycle lengths in graphical models for iterative decoding.
X. Ge,
D. Eppstein, and
P. Smyth.
arXiv:cs.DM/9907002.
Tech.
Rep. 99-10, ICS, UCI, 1999.
IEEE Int. Symp. Information
Theory, Sorrento, Italy, 2000.
IEEE Trans. Information Theory 47 (6): 2549–2553, 2001.
We compute the expected numbers of short cycles of each length in certain classes of random graphs used for turbocodes, estimate the probability that there are no such short cycles involving a given vertex, and experimentally verify our estimates. The scarcity of short cycles may help explain the empirically observed accuracy of belief-propagation based error-correction algorithms. Note, the TR, conference, and journal versions of this paper have slightly different titles.
Fast approximation of centrality.
D. Eppstein and
J. Wang.
arXiv:cs.DS/0009005.
12th ACM-SIAM Symp. Discrete Algorithms,
Washington, 2001, pp. 228–229.
J. Graph Algorithms & Applications 8 (1): 39–45, 2004.
We use random sampling to quickly estimate, for each vertex in a graph, the average distance to all other vertices.
A steady state model for graph power laws.
D. Eppstein and
J. Wang.
2nd Int.
Worksh. Web Dynamics, Honolulu, 2002.
arXiv:cs.DM/0204001.
We propose a random graph model that (empirically) appears to have a power law degree distribution. Unlike previous models, our model is based on a Markov process rather than incremental growth. We compare our model with others in its ability to predict web graph clustering behavior.