<?xml version="1.0" encoding="UTF-8"?>
 <rdf:RDF xmlns="http://purl.org/rss/1.0/" xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:taxo="http://purl.org/rss/1.0/modules/taxonomy/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:cc="http://web.resource.org/cc/" xmlns:syn="http://purl.org/rss/1.0/modules/syndication/" xmlns:admin="http://webns.net/mvcb/">
  <channel rdf:about="http://pinboard.in">
    <title>Pinboard (cshalizi)</title>
    <link>https://pinboard.in/u:cshalizi/public/</link>
    <description>recent bookmarks from cshalizi</description>
    <items>
      <rdf:Seq>	<rdf:li rdf:resource="https://arxiv.org/abs/2503.09299"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2503.03047"/>
	<rdf:li rdf:resource="https://openreview.net/forum?id=S9jem2KZVr"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2006.07695"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2303.16598"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2105.14244"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2009.07542"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2101.07587"/>
	<rdf:li rdf:resource="https://projecteuclid.org/euclid.ejs/1609902191"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2009.05150"/>
	<rdf:li rdf:resource="https://projecteuclid.org/euclid.ss/1608541216"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2012.08444"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2012.05644"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2007.14365"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1708.02107"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1909.02900"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1907.13630"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1903.06936"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1805.07042"/>
	<rdf:li rdf:resource="https://projecteuclid.org/euclid.aos/1558425649"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1410.5837"/>
	<rdf:li rdf:resource="https://projecteuclid.org/euclid.aop/1176989128"/>
	<rdf:li rdf:resource="https://papers.nips.cc/paper/4081-empirical-bernstein-inequalities-for-u-statistics"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1504.04580"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1508.06675"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1507.02925"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1507.04118"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1505.07478"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1506.06162"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1506.00669"/>
	<rdf:li rdf:resource="http://www.ams.org/journals/proc/1964-015-05/S0002-9939-1964-0168712-3/"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1403.3736"/>
	<rdf:li rdf:resource="http://www.sciencedirect.com/science/article/pii/0047259X89900924"/>
	<rdf:li rdf:resource="http://link.springer.com/article/10.1023/A:1021692202530"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1403.0598"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1401.1137"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1401.3915"/>
	<rdf:li rdf:resource="http://www.cs.huji.ac.il/~werman/Papers/cmds.pdf"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1105.5332"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1402.1888"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1401.2906"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1312.5306"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1310.0532"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1310.1495"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1311.1731"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1310.6150"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1309.5936"/>
	<rdf:li rdf:resource="http://www.stat.tamu.edu/~carroll/ftp/2002.papers.directory/berry_ruppert_carroll.pdf"/>
	<rdf:li rdf:resource="http://biomet.oxfordjournals.org/content/86/3/541.short"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1306.6709"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1306.3524"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1201.3861"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1302.0870"/>
	<rdf:li rdf:resource="http://www.ams.org/bookstore-getitem/item=COLL-60"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1302.4615"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1010.4202"/>
	<rdf:li rdf:resource="http://books.nips.cc/papers/files/nips25/NIPS2012_0487.pdf"/>
	<rdf:li rdf:resource="http://pre.aps.org/abstract/PRE/v68/i3/e036112"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1212.4093"/>
	<rdf:li rdf:resource="http://www.stat.washington.edu/people/dcpj/_static/DirectedEmbedding.pdf"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/0902.0132"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/math.CO/0408173"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1206.2380"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1203.2269"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1201.5871"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1202.3123"/>
	<rdf:li rdf:resource="http://projecteuclid.org/DPubS?service=UI&amp;version=1.0&amp;verb=Display&amp;handle=euclid.aos/1321020525"/>
	<rdf:li rdf:resource="http://ergodicity.net/2011/10/30/banff-blog/"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1110.5383"/>
	<rdf:li rdf:resource="http://projecteuclid.org/DPubS?service=UI&amp;version=1.0&amp;verb=Display&amp;handle=euclid.ejs/1319028571"/>
      </rdf:Seq>
    </items>
  </channel><item rdf:about="https://arxiv.org/abs/2503.09299">
    <title>[2503.09299] Low-Rank Graphon Estimation: Theory and Applications to Graphon Games</title>
    <dc:date>2025-04-09T14:17:10+00:00</dc:date>
    <link>https://arxiv.org/abs/2503.09299</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["This paper tackles the challenge of estimating a low-rank graphon from sampled network data, employing a singular value thresholding (SVT) estimator to create a piecewise-constant graphon based on the network's adjacency matrix. Under certain assumptions about the graphon's structural properties, we establish bounds on the operator norm distance between the true graphon and its estimator, as well as on the rank of the estimated graphon. In the second part of the paper, we apply our estimator to graphon games. We derive bounds on the suboptimality of interventions in the social welfare problem in graphon games when the intervention is based on the estimated graphon. These bounds are expressed in terms of the operator norm of the difference between the true and estimated graphons. We also emphasize the computational benefits of using the low-rank estimated graphon to solve these problems."]]></description>
<dc:subject>to:NB network_data_analysis re:smoothing_adjacency_matrices low-rank_approximation</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:4a5fdd1f720b/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:low-rank_approximation"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2503.03047">
    <title>[2503.03047] Stochastic block models with many communities and the Kesten--Stigum bound</title>
    <dc:date>2025-04-09T14:14:39+00:00</dc:date>
    <link>https://arxiv.org/abs/2503.03047</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We study the inference of communities in stochastic block models with a growing number of communities. For block models with n vertices and a fixed number of communities q, it was predicted in Decelle et al. (2011) that there are computationally efficient algorithms for recovering the communities above the Kesten--Stigum (KS) bound and that efficient recovery is impossible below the KS bound. This conjecture has since stimulated a lot of interest, with the achievability side proven in a line of research that culminated in the work of Abbe and Sandon (2018). Conversely, recent work by Sohn and Wein (2025) provides evidence for the hardness part using the low-degree paradigm.
"In this paper we investigate community recovery in the regime q=qn→∞ as n→∞ where no such predictions exist. We show that efficient inference of communities remains possible above the KS bound. Furthermore, we show that recovery of block models is low-degree hard below the KS bound when the number of communities satisfies q≪n‾√. Perhaps surprisingly, we find that when q≫n‾√, there is an efficient algorithm based on non-backtracking walks for recovery even below the KS bound. We identify a new threshold and ask if it is the threshold for efficient recovery in this regime. Finally, we show that detection is easy and identify (up to a constant) the information-theoretic threshold for community recovery as the number of communities q diverges.
"Our low-degree hardness results also naturally have consequences for graphon estimation, improving results of Luo and Gao (2024)."]]></description>
<dc:subject>to:NB community_discovery network_data_analysis graphons re:smoothing_adjacency_matrices</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:2fa03337b383/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:community_discovery"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graphons"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://openreview.net/forum?id=S9jem2KZVr">
    <title>A Simple Latent Variable Model for Graph Learning and Inference | OpenReview</title>
    <dc:date>2025-03-08T14:04:47+00:00</dc:date>
    <link>https://openreview.net/forum?id=S9jem2KZVr</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We introduce a probabilistic latent variable model for graphs that generalizes both the established graphon and stochastic block models. This naive histogram AHK model is simple and versatile, and we demonstrate its use for disparate tasks including complex predictive inference usually not supported by other approaches, and graph generation. We analyze the tradeoffs entailed by the simplicity of the model, which imposes certain limitations on expressivity on the one hand, but on the other hand leads to robust generalization capabilities to graph sizes different from what was seen in the training data."]]></description>
<dc:subject>to:NB stochastic_block_models graphons re:smoothing_adjacency_matrices jaeger.manfred schulte.oliver to_read inference_to_latent_objects relational_learning</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:e826d2031bb8/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:stochastic_block_models"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graphons"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:jaeger.manfred"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:schulte.oliver"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:inference_to_latent_objects"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:relational_learning"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2006.07695">
    <title>[2006.07695] Learning Sparse Graphons and the Generalized Kesten-Stigum Threshold</title>
    <dc:date>2025-01-06T20:24:09+00:00</dc:date>
    <link>https://arxiv.org/abs/2006.07695</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["The problem of learning graphons has attracted considerable attention across several scientific communities, with significant progress over the recent years in sparser regimes. Yet, the current techniques still require diverging degrees in order to succeed with efficient algorithms in the challenging cases where the local structure of the graph is homogeneous. This paper provides an efficient algorithm to learn graphons in the constant expected degree regime. The algorithm is shown to succeed in estimating the rank-k projection of a graphon in the L2 metric if the top k eigenvalues of the graphon satisfy a generalized Kesten-Stigum condition."]]></description>
<dc:subject>to:NB to_read graph_limits re:smoothing_adjacency_matrices sds_icsd_search</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:db19a4928104/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_limits"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:sds_icsd_search"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2303.16598">
    <title>[2303.16598] Robust recovery of Robinson $L^p$-graphons</title>
    <dc:date>2023-04-22T13:54:22+00:00</dc:date>
    <link>https://arxiv.org/abs/2303.16598</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["In this paper, we study the Robinson graphon completion/recovery problem for the class of Lp-graphons. We introduce a function Λ on the space of Lp-graphons, which measures the extent to which a graphon w exhibits the Robinson property: for all x<y<z, w(x,z)≤min{w(x,y),w(y,z)}. We prove that the function Λ satisfies the following: (1) Λ is compatible with the cut-norm, in the sense that if two graphons are close in the cut-norm, then their Λ values are close; and (2) when p>5, every Lp-graphon w can be approximated by a Robinson graphon, with error of the approximation bounded in terms of \IN{Λ(w)}. When w is a noisy version of a Robinson graphon, our method provides a concrete formula for recovering the Robinson graphon approximating w in cut-norm."]]></description>
<dc:subject>re:smoothing_adjacency_matrices graphons network_data_analysis scooped? to_read in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:2651f1bebb02/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graphons"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:scooped?"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2105.14244">
    <title>[2105.14244] Learning Graphon Autoencoders for Generative Graph Modeling</title>
    <dc:date>2021-06-01T17:48:16+00:00</dc:date>
    <link>https://arxiv.org/abs/2105.14244</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Graphon is a nonparametric model that generates graphs with arbitrary sizes and can be induced from graphs easily. Based on this model, we propose a novel algorithmic framework called \textit{graphon autoencoder} to build an interpretable and scalable graph generative model. This framework treats observed graphs as induced graphons in functional space and derives their latent representations by an encoder that aggregates Chebshev graphon filters. A linear graphon factorization model works as a decoder, leveraging the latent representations to reconstruct the induced graphons (and the corresponding observed graphs). We develop an efficient learning algorithm to learn the encoder and the decoder, minimizing the Wasserstein distance between the model and data distributions. This algorithm takes the KL divergence of the graph distributions conditioned on different graphons as the underlying distance and leads to a reward-augmented maximum likelihood estimation. The graphon autoencoder provides a new paradigm to represent and generate graphs, which has good generalizability and transferability."]]></description>
<dc:subject>to:NB graphons re:smoothing_adjacency_matrices statistics</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:6dae79d57286/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graphons"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2009.07542">
    <title>[2009.07542] Perturbation expansions and error bounds for the truncated singular value decomposition</title>
    <dc:date>2021-06-01T13:36:06+00:00</dc:date>
    <link>https://arxiv.org/abs/2009.07542</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Truncated singular value decomposition is a reduced version of the singular value decomposition in which only a few largest singular values are retained. This paper presents a novel perturbation analysis for the truncated singular value decomposition for real matrices. First, we describe perturbation expansions for the singular value truncation of order r. We extend perturbation results for the singular subspace decomposition to derive the first-order perturbation expansion of the truncated operator about a matrix with rank greater than or equal to r. Observing that the first-order expansion can be greatly simplified when the matrix has exact rank r, we further show that the singular value truncation admits a simple second-order perturbation expansion about a rank-r matrix. Second, we introduce the first-known error bound on the linear approximation of the truncated singular value decomposition of a perturbed rank-r matrix. Our bound only depends on the least singular value of the unperturbed matrix and the norm of the perturbation matrix. Intriguingly, while the singular subspaces are known to be extremely sensitive to additive noises, the newly established error bound holds universally for perturbations with arbitrary magnitude. Finally, we demonstrate an application of our results to the analysis of the mean squared error associated with the TSVD-based matrix denoising solution."]]></description>
<dc:subject>to:NB linear_algebra re:smoothing_adjacency_matrices</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:2331bbfe0da7/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:linear_algebra"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2101.07587">
    <title>[2101.07587] Can smooth graphons in several dimensions be represented by smooth graphons on $[0,1]$?</title>
    <dc:date>2021-01-22T05:58:03+00:00</dc:date>
    <link>https://arxiv.org/abs/2101.07587</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["A graphon that is defined on [0,1]d and is Hölder(α) continuous for some d≥2 and α∈(0,1] can be represented by a graphon on [0,1] that is Hölder(α/d) continuous. We give examples that show that this reduction in smoothness to α/d is the best possible, for any d and α; for α=1, the example is a dot product graphon and shows that the reduction is the best possible even for graphons that are polynomials.
"A motivation for studying the smoothness of graphon functions is that this represents a key assumption in non-parametric statistical network analysis. Our examples show that making a smoothness assumption in a particular dimension is not equivalent to making it in any other latent dimension."

--- How is it possible that it's smooth _at all_?!?]]></description>
<dc:subject>to:NB to_read graphons re:smoothing_adjacency_matrices olhede.sofia janson.svante</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:aa3b66091676/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graphons"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:olhede.sofia"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:janson.svante"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://projecteuclid.org/euclid.ejs/1609902191">
    <title>Naulet , Roy , Sharma , Veitch : Bootstrap estimators for the tail-index and for the count statistics of graphex processes</title>
    <dc:date>2021-01-06T17:11:17+00:00</dc:date>
    <link>https://projecteuclid.org/euclid.ejs/1609902191</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Graphex processes resolve some pathologies in traditional random graph models, notably, providing models that are both projective and allow sparsity. Most of the literature on graphex processes study them from a probabilistic point of view. Techniques for inferring the parameter of these processes – the so-called graphon – are still marginal; exceptions are a few papers considering parametric families of graphons. Nonparametric estimation remains unconsidered. In this paper, we propose estimators for a selected choice of functionals of the graphon. Our estimators originate from the subsampling theory for graphex processes, hence can be seen as a form of bootstrap procedure."]]></description>
<dc:subject>to:NB graph_limits network_data_analysis statistics re:bootstrapping_graphs re:smoothing_adjacency_matrices to_read veitch.victor</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:1307a7a47e83/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_limits"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:bootstrapping_graphs"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:veitch.victor"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2009.05150">
    <title>[2009.05150] Inference for high-dimensional exchangeable arrays</title>
    <dc:date>2021-01-03T19:55:54+00:00</dc:date>
    <link>https://arxiv.org/abs/2009.05150</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We consider inference for high-dimensional exchangeable arrays where the dimension may be much larger than the cluster sizes. Specifically, we consider separately and jointly exchangeable arrays that correspond to multiway clustered and polyadic data, respectively. Such exchangeable arrays have seen a surge of applications in empirical economics. However, both exchangeability concepts induce highly complicated dependence structures, which poses a significant challenge for inference in high dimensions. In this paper, we first derive high-dimensional central limit theorems (CLTs) over the rectangles for the exchangeable arrays. Building on the high-dimensional CLTs, we develop novel multiplier bootstraps for the exchangeable arrays and derive their finite sample error bounds in high dimensions. The derivations of these theoretical results rely on new technical tools such as Hoeffding-type decomposition and maximal inequalities for the degenerate components in the Hoeffiding-type decomposition for the exchangeable arrays. We illustrate applications of our bootstrap methods to robust inference in demand analysis, robust inference in extended gravity analysis, uniform confidence bands for density estimation with network data, and penalty choice for ℓ1-penalized regression under multiway cluster sampling."]]></description>
<dc:subject>to:NB exchangeability network_data_analysis high-dimensional_statistics statistics to_read re:smoothing_adjacency_matrices</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:cab87c641900/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:exchangeability"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:high-dimensional_statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://projecteuclid.org/euclid.ss/1608541216">
    <title>Gao , Ma : Minimax Rates in Network Analysis: Graphon Estimation, Community Detection and Hypothesis Testing</title>
    <dc:date>2020-12-21T14:11:01+00:00</dc:date>
    <link>https://projecteuclid.org/euclid.ss/1608541216</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["This paper surveys some recent developments in fundamental limits and optimal algorithms for network analysis. We focus on minimax optimal rates in three fundamental problems of network analysis: graphon estimation, community detection and hypothesis testing. For each problem, we review state-of-the-art results in the literature followed by general principles behind the optimal procedures that lead to minimax estimation and testing. This allows us to connect problems in network analysis to other statistical inference problems from a general perspective."]]></description>
<dc:subject>to:NB network_data_analysis graph_limits hypothesis_testing minimax nonparametrics re:smoothing_adjacency_matrices community_discovery to_read</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:4146f1114577/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_limits"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:hypothesis_testing"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:minimax"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:nonparametrics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:community_discovery"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2012.08444">
    <title>[2012.08444] Minimax Risk and Uniform Convergence Rates for Nonparametric Dyadic Regression</title>
    <dc:date>2020-12-16T15:11:23+00:00</dc:date>
    <link>https://arxiv.org/abs/2012.08444</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Let i=1,…,N index a simple random sample of units drawn from some large population. For each unit we observe the vector of regressors Xi and, for each of the N(N−1) ordered pairs of units, an outcome Yij. The outcomes Yij and Ykl are independent if their indices are disjoint, but dependent otherwise (i.e., "dyadically dependent"). Let Wij=(X′i,X′j)′; using the sampled data we seek to construct a nonparametric estimate of the mean regression function g(Wij)≡def𝔼[Yij∣∣Xi,Xj].
"We present two sets of results. First, we calculate lower bounds on the minimax risk for estimating the regression function at (i) a point and (ii) under the infinity norm. Second, we calculate (i) pointwise and (ii) uniform convergence rates for the dyadic analog of the familiar Nadaraya-Watson (NW) kernel regression estimator. We show that the NW kernel regression estimator achieves the optimal rates suggested by our risk bounds when an appropriate bandwidth sequence is chosen. This optimal rate differs from the one available under iid data: the effective sample size is smaller and dW=dim(Wij) influences the rate differently."]]></description>
<dc:subject>to:NB network_data_analysis regression nonparametrics re:smoothing_adjacency_matrices to_read</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:de76b10c1394/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:regression"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:nonparametrics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2012.05644">
    <title>[2012.05644] Learning Graphons via Structured Gromov-Wasserstein Barycenters</title>
    <dc:date>2020-12-11T17:36:15+00:00</dc:date>
    <link>https://arxiv.org/abs/2012.05644</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We propose a novel and principled method to learn a nonparametric graph model called graphon, which is defined in an infinite-dimensional space and represents arbitrary-size graphs. Based on the weak regularity lemma from the theory of graphons, we leverage a step function to approximate a graphon. We show that the cut distance of graphons can be relaxed to the Gromov-Wasserstein distance of their step functions. Accordingly, given a set of graphs generated by an underlying graphon, we learn the corresponding step function as the Gromov-Wasserstein barycenter of the given graphs. Furthermore, we develop several enhancements and extensions of the basic algorithm, e.g., the smoothed Gromov-Wasserstein barycenter for guaranteeing the continuity of the learned graphons and the mixed Gromov-Wasserstein barycenters for learning multiple structured graphons. The proposed approach overcomes drawbacks of prior state-of-the-art methods, and outperforms them on both synthetic and real-world data. "]]></description>
<dc:subject>to:NB to_read scooped? graphons re:smoothing_adjacency_matrices</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:1f74b8ac44a1/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:scooped?"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graphons"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2007.14365">
    <title>[2007.14365] Tractably Modelling Dependence in Networks Beyond Exchangeability</title>
    <dc:date>2020-09-09T17:48:31+00:00</dc:date>
    <link>https://arxiv.org/abs/2007.14365</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We propose a general framework for modelling network data that is designed to describe aspects of non-exchangeable networks. Conditional on latent (unobserved) variables, the edges of the network are generated by their finite growth history (with latent orders) while the marginal probabilities of the adjacency matrix are modeled by a generalization of a graph limit function (or a graphon). In particular, we study the estimation, clustering and degree behavior of the network in our setting. We determine (i) the minimax estimator of a composite graphon with respect to squared error loss; (ii) that spectral clustering is able to consistently detect the latent membership when the block-wise constant composite graphon is considered under additional conditions; and (iii) we are able to construct models with heavy-tailed empirical degrees under specific scenarios and parameter choices. This explores why and under which general conditions non-exchangeable network data can be described by a stochastic block model. The new modelling framework is able to capture empirically important characteristics of network data such as sparsity combined with heavy tailed degree distribution, and add understanding as to what generative mechanisms will make them arise.
"Keywords: statistical network analysis, exchangeable arrays, stochastic block model, nonlinear stochastic processes."]]></description>
<dc:subject>to:NB network_data_analysis graphons to_read re:smoothing_adjacency_matrices wolfe.patrick olhede.sofia</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:20c5aa187bff/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graphons"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:wolfe.patrick"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:olhede.sofia"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1708.02107">
    <title>[1708.02107] Adaptive Estimation of Nonparametric Geometric Graphs</title>
    <dc:date>2019-10-01T17:33:41+00:00</dc:date>
    <link>https://arxiv.org/abs/1708.02107</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["This article studies the recovery of graphons when they are convolution kernels on compact (symmetric) metric spaces. This case is of particular interest since it covers the situation where the probability of an edge depends only on some unknown nonparametric function of the distance between latent points, referred to as Nonparametric Geometric Graphs (NGG).
"In this setting, adaptive estimation of NGG is possible using a spectral procedure combined with a Goldenshluger-Lepski adaptation method. The latent spaces covered by our framework encompass (among others) compact symmetric spaces of rank one, namely real spheres and projective spaces. For these latter, explicit computations of the eigen-basis and of the model complexity can be achieved, leading to quantitative non-asymptotic results. The time complexity of our method scales cubicly in the size of the graph and exponentially in the regularity of the graphon. Hence, this paper offers an algorithmically and theoretically efficient procedure to estimate smooth NGG.
"As a by product, this paper shows a non-asymptotic concentration result on the spectrum of integral operators defined by symmetric kernels (not necessarily positive)."]]></description>
<dc:subject>to:NB network_data_analysis nonparametrics statistics re:smoothing_adjacency_matrices to_read</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:c5e986b823fa/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:nonparametrics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1909.02900">
    <title>[1909.02900] On the Estimation of Network Complexity: Dimension of Graphons</title>
    <dc:date>2019-09-09T03:45:40+00:00</dc:date>
    <link>https://arxiv.org/abs/1909.02900</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Network complexity has been studied for over half a century and has found a wide range of applications. Many methods have been developed to characterize and estimate the complexity of networks. However, there has been little research with statistical guarantees. In this paper, we develop a statistical theory of graph complexity in a general model of random graphs, the so-called graphon model. Given a graphon, we endow the latent space of the nodes with the so-called neighborhood distance that measures the propensity of two nodes to be connected with similar nodes. Our complexity index is then based on the covering number and the Minkowski dimension of (a purified version of) this metric space. Although the latent space is not identifiable, these indices turn out to be identifiable. This notion of complexity has simple interpretations on popular examples of random graphs: it matches the number of communities in stochastic block models; the dimension of the Euclidean space in random geometric graphs; the regularity of the link function in Hölder graphon models. From a single observation of the graph, we construct an estimator of the neighborhood-distance and show universal non-asymptotic bounds for its risk, matching minimax lower bounds. Based on this estimated distance, we compute the corresponding covering number and Minkowski dimension and we provide optimal non-asymptotic error bounds for these two plug-in estimators."]]></description>
<dc:subject>to:NB to_read complexity_measures graph_limits network_data_analysis re:smoothing_adjacency_matrices</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:47ae48949e23/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:complexity_measures"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_limits"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1907.13630">
    <title>[1907.13630] Kernel Density Estimation for Undirected Dyadic Data</title>
    <dc:date>2019-08-02T15:20:07+00:00</dc:date>
    <link>https://arxiv.org/abs/1907.13630</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We study nonparametric estimation of density functions for undirected dyadic random variables (i.e., random variables defined for all n\overset{def}{\equiv}\tbinom{N}{2} unordered pairs of agents/nodes in a weighted network of order N). These random variables satisfy a local dependence property: any random variables in the network that share one or two indices may be dependent, while those sharing no indices in common are independent. In this setting, we show that density functions may be estimated by an application of the kernel estimation method of Rosenblatt (1956) and Parzen (1962). We suggest an estimate of their asymptotic variances inspired by a combination of (i) Newey's (1994) method of variance estimation for kernel estimators in the "monadic" setting and (ii) a variance estimator for the (estimated) density of a simple network first suggested by Holland and Leinhardt (1976). More unusual are the rates of convergence and asymptotic (normal) distributions of our dyadic density estimates. Specifically, we show that they converge at the same rate as the (unconditional) dyadic sample mean: the square root of the number, N, of nodes. This differs from the results for nonparametric estimation of densities and regression functions for monadic data, which generally have a slower rate of convergence than their corresponding sample mean."]]></description>
<dc:subject>to:NB density_estimation network_data_analysis nonparametrics kernel_methods re:smoothing_adjacency_matrices</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:9f0623d7f460/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:density_estimation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:nonparametrics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:kernel_methods"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1903.06936">
    <title>[1903.06936] Bayesian and Spline based Approaches for (EM based) Graphon Estimation</title>
    <dc:date>2019-07-31T15:21:25+00:00</dc:date>
    <link>https://arxiv.org/abs/1903.06936</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["The paper proposes the estimation of a graphon function for network data using principles of the EM algorithm. The approach considers both, variability with respect to ordering the nodes of a network and estimation of the unique representation of a graphon. To do so (linear) B-splines are used, which allows to easily accommodate constraints in the estimation routine so that the estimated graphon fulfills the canonical representation, meaning its univariate margin is monotonic. The graphon estimate itself allows to apply Bayesian ideas to explore both, the degree distribution and the ordering of the nodes with respect to their degree. Variability and uncertainty is taken into account using MCMC techniques. Combining both steps gives an EM based approach for graphon estimation."

GODDAMIT.]]></description>
<dc:subject>to:NB to_read graph_limits network_data_analysis nonparametrics statistics re:smoothing_adjacency_matrices scooped?</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:cb0eef6743fc/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_limits"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:nonparametrics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:scooped?"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1805.07042">
    <title>[1805.07042] Graphon estimation via nearest neighbor algorithm and 2D fused lasso denoising</title>
    <dc:date>2019-06-21T15:42:52+00:00</dc:date>
    <link>https://arxiv.org/abs/1805.07042</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We propose a class of methods for graphon estimation based on exploiting connections with nonparametric regression. The idea is to construct an ordering of the nodes in the network, similar in spirit to Chan and Airoldi (2014). However, rather than only considering orderings based on the empirical degree as in Chan and Airoldi (2014), we use the nearest neighbor algorithm which is an approximating solution to the traveling salesman problem. This in turn can handle general distances d̂  between the nodes, something that allows us to incorporate rich information of the network. Once an ordering is constructed, we formulate a 2D grid graph denoising problem that we solve through fused lasso regularization. For particular choices of the metric d̂ , we show that the corresponding two-step estimator can attain competitive rates when the true model is the stochastic block model, and when the underlying graphon is piecewise Hölder or it has bounded variation."]]></description>
<dc:subject>to:NB graph_limits network_data_analysis statistics re:smoothing_adjacency_matrices</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:30fe3be3dad2/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_limits"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://projecteuclid.org/euclid.aos/1558425649">
    <title>Pensky : Dynamic network models and graphon estimation</title>
    <dc:date>2019-05-26T22:13:05+00:00</dc:date>
    <link>https://projecteuclid.org/euclid.aos/1558425649</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["In the present paper, we consider a dynamic stochastic network model. The objective is estimation of the tensor of connection probabilities ΛΛ when it is generated by a Dynamic Stochastic Block Model (DSBM) or a dynamic graphon. In particular, in the context of the DSBM, we derive a penalized least squares estimator ΛˆΛ^ of ΛΛ and show that ΛˆΛ^ satisfies an oracle inequality and also attains minimax lower bounds for the risk. We extend those results to estimation of ΛΛ when it is generated by a dynamic graphon function. The estimators constructed in the paper are adaptive to the unknown number of blocks in the context of the DSBM or to the smoothness of the graphon function. The technique relies on the vectorization of the model and leads to much simpler mathematical arguments than the ones used previously in the stationary set up. In addition, all results in the paper are nonasymptotic and allow a variety of extensions."]]></description>
<dc:subject>to:NB to_read graph_limits nonparametrics network_data_analysis re:smoothing_adjacency_matrices</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:276ac9ad5cc1/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_limits"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:nonparametrics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1410.5837">
    <title>[1410.5837] Rate-optimal graphon estimation</title>
    <dc:date>2016-07-12T00:05:12+00:00</dc:date>
    <link>http://arxiv.org/abs/1410.5837</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Network analysis is becoming one of the most active research areas in statistics. Significant advances have been made recently on developing theories, methodologies and algorithms for analyzing networks. However, there has been little fundamental study on optimal estimation. In this paper, we establish optimal rate of convergence for graphon estimation. For the stochastic block model with k clusters, we show that the optimal rate under the mean squared error is n−1logk+k2/n2. The minimax upper bound improves the existing results in literature through a technique of solving a quadratic equation. When k≤nlogn‾‾‾‾‾‾√, as the number of the cluster k grows, the minimax rate grows slowly with only a logarithmic order n−1logk. A key step to establish the lower bound is to construct a novel subset of the parameter space and then apply Fano's lemma, from which we see a clear distinction of the nonparametric graphon estimation problem from classical nonparametric regression, due to the lack of identifiability of the order of nodes in exchangeable random graph models. As an immediate application, we consider nonparametric graphon estimation in a H\"{o}lder class with smoothness α. When the smoothness α≥1, the optimal rate of convergence is n−1logn, independent of α, while for α∈(0,1), the rate is n−2α/(α+1), which is, to our surprise, identical to the classical nonparametric rate."]]></description>
<dc:subject>re:smoothing_adjacency_matrices network_data_analysis statistics graph_limits to:NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:0e830503e9e7/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_limits"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://projecteuclid.org/euclid.aop/1176989128">
    <title>Arcones , Gine : Limit Theorems for $U$-Processes</title>
    <dc:date>2015-12-09T00:27:53+00:00</dc:date>
    <link>https://projecteuclid.org/euclid.aop/1176989128</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Necessary and sufficient conditions for the law of large numbers and sufficient conditions for the central limit theorem for U-processes are given. These conditions are in terms of random metric entropies. The CLT and LLN for VC subgraph classes of functions as well as for classes satisfying bracketing conditions follow as consequences of the general results. In particular, Liu's simplicial depth process satisfies both the LLN and the CLT. Among the techniques used, randomization, decoupling inequalities, integrability of Gaussian and Rademacher chaos and exponential inequalities for U-statistics should be mentioned."]]></description>
<dc:subject>u-statistics empirical_processes deviation_inequalities vc-dimension central_limit_theorem re:smoothing_adjacency_matrices in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:fbf2713f12b2/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:u-statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:empirical_processes"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:deviation_inequalities"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:vc-dimension"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:central_limit_theorem"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://papers.nips.cc/paper/4081-empirical-bernstein-inequalities-for-u-statistics">
    <title>Empirical Bernstein Inequalities for U-Statistics</title>
    <dc:date>2015-12-09T00:26:24+00:00</dc:date>
    <link>https://papers.nips.cc/paper/4081-empirical-bernstein-inequalities-for-u-statistics</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We present original empirical Bernstein inequalities for U-statistics with bounded symmetric kernels q. They are expressed with respect to empirical estimates of either the variance of q or the conditional variance that appears in the Bernstein-type inequality for U-statistics derived by Arcones [2]. Our result subsumes other existing empirical Bernstein inequalities, as it reduces to them when U-statistics of order 1 are considered. In addition, it is based on a rather direct argument using two applications of the same (non-empirical) Bernstein inequality for U-statistics. We discuss potential applications of our new inequalities, especially in the realm of learning ranking/scoring functions. In the process, we exhibit an efficient procedure to compute the variance estimates for the special case of bipartite ranking that rests on a sorting argument. We also argue that our results may provide test set bounds and particularly interesting empirical racing algorithms for the problem of online learning of scoring functions."]]></description>
<dc:subject>u-statistics statistics estimation deviation_inequalities re:smoothing_adjacency_matrices in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:b134f56ca494/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:u-statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:estimation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:deviation_inequalities"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1504.04580">
    <title>[1504.04580] Robust estimation of U-statistics</title>
    <dc:date>2015-12-09T00:24:14+00:00</dc:date>
    <link>http://arxiv.org/abs/1504.04580</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["An important part of the legacy of Evarist Gin\'e is his fundamental contributions to our understanding of U-statistics and U-processes. In this paper we discuss the estimation of the mean of multivariate functions in case of possibly heavy-tailed distributions. In such situations, reliable estimates of the mean cannot be obtained by usual U-statistics. We introduce a new estimator, based on the so-called median-of-means technique. We develop performance bounds for this new estimator that generalizes an estimate of Arcones and Gin\'e (1993), showing that the new estimator performs, under minimal moment conditions, as well as classical U-statistics for bounded random variables. We discuss an application of this estimator to clustering."]]></description>
<dc:subject>heavy_tails statistics estimation deviation_inequalities re:smoothing_adjacency_matrices u-statistics in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:8dc1640ac0d6/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:heavy_tails"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:estimation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:deviation_inequalities"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:u-statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1508.06675">
    <title>[1508.06675] Consistent nonparametric estimation for heavy-tailed sparse graphs</title>
    <dc:date>2015-09-13T19:58:16+00:00</dc:date>
    <link>http://arxiv.org/abs/1508.06675</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We study graphons as a non-parametric generalization of stochastic block models, and show how to obtain compactly represented estimators for sparse networks in this framework. Our algorithms and analysis go beyond previous work in several ways. First, we relax the usual boundedness assumption for the generating graphon and instead treat arbitrary integrable graphons, so that we can handle networks with long tails in their degree distributions. Second, again motivated by real-world applications, we relax the usual assumption that the graphon is defined on the unit interval, to allow latent position graphs where the latent positions live in a more general space, and we characterize identifiability for these graphons and their underlying position spaces. 
"We analyze three algorithms. The first is a least squares algorithm, which gives an approximation we prove to be consistent for all square-integrable graphons, with errors expressed in terms of the best possible stochastic block model approximation to the generating graphon. Next, we analyze a generalization based on the cut norm, which works for any integrable graphon (not necessarily square-integrable). Finally, we show that clustering based on degrees works whenever the underlying degree distribution is absolutely continuous with respect to Lebesgue measure. Unlike the previous two algorithms, this third one runs in polynomial time."]]></description>
<dc:subject>to_read graph_limits network_data_analysis re:smoothing_adjacency_matrices cohn.henry chayes.jennifer borgs.christian heard_the_talk to_teach:graphons in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:472625b9cca4/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_limits"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:cohn.henry"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:chayes.jennifer"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:borgs.christian"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:heard_the_talk"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_teach:graphons"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1507.02925">
    <title>[1507.02925] Completely random measures for modelling block-structured sparse networks</title>
    <dc:date>2015-08-05T16:25:29+00:00</dc:date>
    <link>http://arxiv.org/abs/1507.02925</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Many statistical methods for network data parameterize the edge-probability by attributing latent traits to the vertices such as block structure and assume exchangeability in the sense of the Aldous-Hoover representation theorem. Empirical studies of networks indicates that many large, real-world networks have a power-law distribution of the vertices which in turn implies the number of edges scale slower than quadratically in the number of vertices. These assumptions are fundamentally irreconcilable as the Aldous-Hoover theorem implies quadratic scaling of the number of edges. Recently Caron and Fox (2014) proposed the use of a different notion of exchangeability due to Kallenberg (2009) and obtained a network model which admits power-law behaviour while retaining desirable statistical properties, however this model do not capture latent vertex traits such as block-structure. In this work we re-introduce the use of block-structure for network modelling in the new setting and thereby obtain a model which admits the inference of block-structure and edge inhomogeneity. We derive a simple expression for the likelihood and an efficient sampling method. The obtained model is not significantly more difficult to implement than existing methods and performs well on real network datasets."]]></description>
<dc:subject>graph_limits network_data_analysis statistics re:smoothing_adjacency_matrices in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:ac4c2b52fe92/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_limits"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1507.04118">
    <title>[1507.04118] Oracle inequalities for network models and sparse graphon estimation</title>
    <dc:date>2015-08-05T16:20:01+00:00</dc:date>
    <link>http://arxiv.org/abs/1507.04118</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Inhomogeneous random graph models encompass many network models such as stochastic block models and latent position models. In this paper, we study two estimators -- the ordinary block constant least squares estimator, and its restricted version. We show that they satisfy oracle inequalities with respect to the block constant oracle. As a consequence, we derive optimal rates of estimation of the probability matrix. Our results cover the important setting of sparse networks. Nonparametric rates for graphon estimation in the L2 norm are also derived when the probability matrix is sampled according to a graphon model. The results shed light on the differences between estimation under the empirical loss (the probability matrix estimation) and under the integrated loss (the graphon estimation)."]]></description>
<dc:subject>to:NB network_data_analysis graph_limits statistics minimax estimation re:smoothing_adjacency_matrices</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:a511970b5a6d/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_limits"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:minimax"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:estimation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1505.07478">
    <title>[1505.07478] Generalized communities in networks</title>
    <dc:date>2015-07-14T12:57:41+00:00</dc:date>
    <link>http://arxiv.org/abs/1505.07478</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["A substantial volume of research has been devoted to studies of community structure in networks, but communities are not the only possible form of large-scale network structure. Here we describe a broad extension of community structure that encompasses traditional communities but includes a wide range of generalized structural patterns as well. We describe a principled method for detecting this generalized structure in empirical network data and demonstrate with real-world examples how it can be used to learn new things about the shape and meaning of networks."]]></description>
<dc:subject>network_data_analysis community_discovery statistics scooped? kith_and_kin newman.mark re:smoothing_adjacency_matrices to_teach:graphons in_NB have_read</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:b11f0d120405/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:community_discovery"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:scooped?"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:kith_and_kin"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:newman.mark"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_teach:graphons"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:have_read"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1506.06162">
    <title>[1506.06162] Private Graphon Estimation for Sparse Graphs</title>
    <dc:date>2015-07-14T09:49:13+00:00</dc:date>
    <link>http://arxiv.org/abs/1506.06162</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We design algorithms for fitting a high-dimensional statistical model to a large, sparse network without revealing sensitive informataion of individual members. Given a sparse input graph G, our algorithms output a node-differentially-private nonparametric block model approximation. By node-differentially-private, we mean that our output hides the insertion or removal of a vertex and all its adjacent edges. If G is an instance of the network obtained from a generative nonparametric model defined in terms of a graphon W, our model guarantees consistency, in the sense that as the number of vertices tends to infinity, the output of our algorithm converges to W in an appropriate version of the L2 norm. In particular, this means we can estimate the sizes of all multi-way cuts in G. 
"Our results hold as long as W is bounded, the average degree of G grows at least like the log of the number of vertices, and the number of blocks goes to infinity at an appropriate rate. We give explicit error bounds in terms of the parameters of the model; in several settings, our bounds improve on or match known nonprivate results."]]></description>
<dc:subject>to:NB graph_limits nonparametrics differential_privacy stochastic_block_models statistics re:smoothing_adjacency_matrices borgs.christian chayes.jennifer</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:1ab606448a32/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_limits"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:nonparametrics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:differential_privacy"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:stochastic_block_models"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:borgs.christian"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:chayes.jennifer"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1506.00669">
    <title>[1506.00669] Concentration and regularization of random graphs</title>
    <dc:date>2015-06-03T15:14:14+00:00</dc:date>
    <link>http://arxiv.org/abs/1506.00669</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["This paper studies how close random graphs are typically to their expectations. We interpret this question through the concentration of the adjacency and Laplacian matrices in the spectral norm. We study inhomogeneous Erd\"os-R\'enyi random graphs on n vertices, where edges form independently and possibly with different probabilities pij. Sparse random graphs whose expected degrees are o(logn) fail to concentrate. The obstruction is caused by vertices with abnormally high and low degrees. We show that concentration can be restored if we regularize the degrees of such vertices, and one can do this is various ways. As an example, let us reweight or remove enough edges to make all degrees bounded above by O(d) where d=maxpnij. Then we show that the resulting adjacency matrix A′ concentrates with the optimal rate: ∥A′−𝔼A∥=O(d‾‾√). Similarly, if we make all degrees bounded below by d by adding weight d/n to all edges, then the resulting Laplacian concentrates with the optimal rate: ∥L(A′)−L(𝔼A′)∥=O(1/d‾‾√). Our approach is based on Grothendieck-Pietsch factorization, using which we construct a new decomposition of random graphs. These results improve and simplify the recent work of L. Levina and the authors. We illustrate the concentration results with an application to the community detection problem in the analysis of networks."]]></description>
<dc:subject>to_read concentration_of_measure graph_theory graph_limits re:smoothing_adjacency_matrices re:network_differences in_NB via:mraginsky</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:c32f3b03c787/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:concentration_of_measure"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_limits"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:network_differences"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:via:mraginsky"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.ams.org/journals/proc/1964-015-05/S0002-9939-1964-0168712-3/">
    <title>Mean oscillation over cubes and Hölder continuity</title>
    <dc:date>2014-11-12T01:19:24+00:00</dc:date>
    <link>http://www.ams.org/journals/proc/1964-015-05/S0002-9939-1964-0168712-3/</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA[So it turns out that my regularity condition is just Holder continuity in integral disguise.  I feel a bit less stupid because it was considered worth a paper to show this, at least once upon a time.]]></description>
<dc:subject>mathematics real_analysis re:smoothing_adjacency_matrices have_read to:NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:89fb532893a4/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:real_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:have_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1403.3736">
    <title>[1403.3736] Differential Calculus on Graphon Space</title>
    <dc:date>2014-06-07T19:38:53+00:00</dc:date>
    <link>http://arxiv.org/abs/1403.3736</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Recently, the theory of dense graph limits has received attention from multiple disciplines including graph theory, computer science, statistical physics, probability, statistics, and group theory. In this paper we initiate the study of the general structure of differentiable graphon parameters F. We derive consistency conditions among the higher G\^ateaux derivatives of F when restricted to the subspace of edge weighted graphs p. Surprisingly, these constraints are rigid enough to imply that the multilinear functionals Λ:np→ℝ satisfying the constraints are determined by a finite set of constants indexed by isomorphism classes of multigraphs with n edges and no isolated vertices. Using this structure theory, we explain the central role that homomorphism densities play in the analysis of graphons, by way of a new combinatorial interpretation of their derivatives. In particular, homomorphism densities serve as the monomials in a polynomial algebra that can be used to approximate differential graphon parameters as Taylor polynomials. These ideas are summarized by our main theorem, which asserts that homomorphism densities t(H,−) where H has at most N edges form a basis for the space of smooth graphon parameters whose (N+1)st derivatives vanish. As a consequence of this theory, we also extend and derive new proofs of linear independence of multigraph homomorphism densities, and characterize homomorphism densities. In addition, we develop a theory of series expansions, including Taylor's theorem for graph parameters and a uniqueness principle for series. We use this theory to analyze questions raised by Lov\'asz, including studying infinite quantum algebras and the connection between right- and left-homomorphism densities."]]></description>
<dc:subject>to:NB graph_limits analysis mathematics to_read re:smoothing_adjacency_matrices</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:faa4dde59619/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_limits"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.sciencedirect.com/science/article/pii/0047259X89900924">
    <title>On the representation theorem for exchangeable arrays</title>
    <dc:date>2014-03-26T14:12:23+00:00</dc:date>
    <link>http://www.sciencedirect.com/science/article/pii/0047259X89900924</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Aldous and Hoover have proved independently that an array X = (Xij, i, j ∈ ) of random variables is exchangeable under separate or joint permutations of rows and columns, iff a.s. Xij≡f(α, ξi, ηj, ξij) or Xij≡f(α, ξi, ξj, ξij), respectively, for some measurable function f: 4→ and some i.i.d. random variables α, ξi, ηj, ξij, i, j∈, or α, ξi, ξij=ξji, 1≤i≤j. Hoover also gave a criterion for two functions f and g as above to give rise to arrays with the same distribution. The aim of this paper is to give an elementary proof of Hoover's result, and to deduce some further equivalence criteria. The present methods will also provide a simple approach to certain conditional properties of exchangeable arrays."]]></description>
<dc:subject>probability exchangeability stochastic_processes kallenberg.olav re:smoothing_adjacency_matrices exchangeable_arrays have_read to_teach:graphons in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:ee3b529ed2e6/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:probability"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:exchangeability"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:stochastic_processes"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:kallenberg.olav"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:exchangeable_arrays"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:have_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_teach:graphons"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://link.springer.com/article/10.1023/A:1021692202530">
    <title>Multivariate Sampling and the Estimation Problem for Exchangeable Arrays - Springer</title>
    <dc:date>2014-03-26T14:10:41+00:00</dc:date>
    <link>http://link.springer.com/article/10.1023/A:1021692202530</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We consider random arrays and the associated empirical distributions obtained by multivariate sampling from a stationary process. Under suitable conditions, one gets convergence toward a separately exchangeable array and its ergodic distribution. The result is related to the statistical problem of estimating the representing function of an exchangeable array. The latter problem is well-posed only for shell-measurable arrays, where the grid processes based on finite sub-arrays form consistent estimates with respect to a suitable norm. In general, the required consistency holds only in the distributional sense for the generated arrays."]]></description>
<dc:subject>stochastic_processes exchangeability statistical_inference_for_stochastic_processes kallenberg.olav re:smoothing_adjacency_matrices network_data_analysis statistics in_NB have_read ergodic_theory to_teach:graphons exchangeable_arrays</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:f9139f894731/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:stochastic_processes"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:exchangeability"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistical_inference_for_stochastic_processes"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:kallenberg.olav"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:have_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:ergodic_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_teach:graphons"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:exchangeable_arrays"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1403.0598">
    <title>[1403.0598] The Structurally Smoothed Graphlet Kernel</title>
    <dc:date>2014-03-10T18:00:40+00:00</dc:date>
    <link>http://arxiv.org/abs/1403.0598</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["A commonly used paradigm for representing graphs is to use a vector that contains normalized frequencies of occurrence of certain motifs or sub-graphs. This vector representation can be used in a variety of applications, such as, for computing similarity between graphs. The graphlet kernel of Shervashidze et al. [32] uses induced sub-graphs of k nodes (christened as graphlets by Przulj [28]) as motifs in the vector representation, and computes the kernel via a dot product between these vectors. One can easily show that this is a valid kernel between graphs. However, such a vector representation suffers from a few drawbacks. As k becomes larger we encounter the sparsity problem; most higher order graphlets will not occur in a given graph. This leads to diagonal dominance, that is, a given graph is similar to itself but not to any other graph in the dataset. On the other hand, since lower order graphlets tend to be more numerous, using lower values of k does not provide enough discrimination ability. We propose a smoothing technique to tackle the above problems. Our method is based on a novel extension of Kneser-Ney and Pitman-Yor smoothing techniques from natural language processing to graphs. We use the relationships between lower order and higher order graphlets in order to derive our method. Consequently, our smoothing algorithm not only respects the dependency between sub-graphs but also tackles the diagonal dominance problem by distributing the probability mass across graphlets. In our experiments, the smoothed graphlet kernel outperforms graph kernels based on raw frequency counts."]]></description>
<dc:subject>to:NB kernel_methods network_data_analysis graph_theory to_read re:smoothing_adjacency_matrices re:network_differences</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:cf5ca26f08a9/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:kernel_methods"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:network_differences"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1401.1137">
    <title>[1401.1137] Bayesian nonparametric models of sparse and exchangeable random graphs</title>
    <dc:date>2014-03-10T00:50:33+00:00</dc:date>
    <link>http://arxiv.org/abs/1401.1137</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Statistical network modeling has focused on representing the graph as a discrete structure, namely the adjacency matrix, and considering the exchangeability of this array. In such cases, the Aldous-Hoover representation theorem (Aldous, 1981; Hoover, 1979) applies and informs us that the graph is necessarily either dense or empty. In this paper, we instead consider representing the graph as a measure on the positive quadrant. For the associated definition of exchangeability in this continuous space, we rely on the Kallenberg representation theorem (Kallenberg, 2005). We show that for certain choices of the specified graph construction, our network process is both exchangeable and sparse with power-law degree distribution. In particular, we build on the framework of completely random measures (CRMs) and use the theory associated with such processes to derive important network properties, such as an urn representation for network simulation. The CRM framework also provides for interpretability of the network model in terms of node-specific sociability parameters, with properties such as sparsity and power-law behavior simply tuned by three hyperparameters. Our theoretical results are explored empirically and compared to common network models."

--- I really need to re-re-read this, because I find myself increasingly confused on each pass through.  How can representing the graph as a point process in R^2 be the key to making it sparse and exchangeable, when the locations on the axes representing the nodes are unidentified?  Why not then just always scale back to [0,1]^2, and have an ordinary graphon?  Hopefully the students will resolve my confusions.]]></description>
<dc:subject>graph_limits nonparametrics stochastic_processes fox.emily re:smoothing_adjacency_matrices to_read statistics in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:22258125b6f2/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_limits"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:nonparametrics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:stochastic_processes"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:fox.emily"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1401.3915">
    <title>[1401.3915] Community Detection in Networks using Graph Distance</title>
    <dc:date>2014-02-20T22:22:55+00:00</dc:date>
    <link>http://arxiv.org/abs/1401.3915</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["The study of networks has received increased attention recently not only from the social sciences and statistics but also from physicists, computer scientists and mathematicians. One of the principal problem in networks is community detection. Many algorithms have been proposed for community finding but most of them do not have have theoretical guarantee for sparse networks and networks close to the phase transition boundary proposed by physicists. There are some exceptions but all have some incomplete theoretical basis. Here we propose an algorithm based on the graph distance of vertices in the network. We give theoretical guarantees that our method works in identifying communities for block models and can be extended for degree-corrected block models and block models with the number of communities growing with number of vertices. Despite favorable simulation results, we are not yet able to conclude that our method is satisfactory for worst possible case. We illustrate on a network of political blogs, Facebook networks and some other networks."]]></description>
<dc:subject>community_discovery network_data_analysis re:smoothing_adjacency_matrices to_read in_NB bickel.peter_j.</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:1d3b71ae36f4/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:community_discovery"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:bickel.peter_j."/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.cs.huji.ac.il/~werman/Papers/cmds.pdf">
    <title>The World is not always Flat or Learning Curved Manifolds</title>
    <dc:date>2014-02-19T23:44:28+00:00</dc:date>
    <link>http://www.cs.huji.ac.il/~werman/Papers/cmds.pdf</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Manifold learning and finding low-dimensional structure in data is an important task. Many algorithms for this purpose embed data in Euclidean space, an approach which is destined to fail on non-flat data. This paper presents a non-iterative algebraic method for embedding the data into hyperbolic and spherical spaces. We argue that these spaces are often better than Euclidean space in capturing the geometry of the data. The approach can be used to extend algorithms such as ISOMAP and SDE to the curved case. We also demonstrate the utility of these embeddings by showing how some of the standard clustering algorithms translate to these curved manifolds."]]></description>
<dc:subject>to_read hyperbolic_geometry manifold_learning multidimensional_scaling re:smoothing_adjacency_matrices principal_components in_NB graph_embedding re:hyperbolic_networks</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:bf83be8b8be0/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:hyperbolic_geometry"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:manifold_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:multidimensional_scaling"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:principal_components"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_embedding"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:hyperbolic_networks"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1105.5332">
    <title>[1105.5332] Multidimensional Scaling in the Poincar'e Disk</title>
    <dc:date>2014-02-19T23:43:50+00:00</dc:date>
    <link>http://arxiv.org/abs/1105.5332</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Multidimensional scaling (MDS) is a class of projective algorithms traditionally used to produce two- or three-dimensional visualizations of datasets consisting of multidimensional objects or interobject distances. Recently, metric MDS has been applied to the problems of graph embedding for the purpose of approximate encoding of edge or path costs using node coordinates in metric space. Several authors have also pointed out that for data with an inherent hierarchical structure, hyperbolic target space may be a more suitable choice for accurate embedding than Euclidean space. In this paper we present the theory and the implementation details of MDS-PD, a metric MDS algorithm designed specifically for the Poincar\'e disk model of the hyperbolic plane. Our construction is based on an approximate hyperbolic line search and exemplifies some of the particulars that need to be addressed when applying iterative optimization methods in a hyperbolic space model. MDS-PD can be used both as a visualization tool and as an embedding algorithm. We provide several examples to illustrate the utility of MDS-PD."]]></description>
<dc:subject>to_read visual_display_of_quantitative_information hyperbolic_geometry network_data_analysis optimization multidimensional_scaling re:smoothing_adjacency_matrices in_NB re:hyperbolic_networks</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:1e670914899f/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:visual_display_of_quantitative_information"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:hyperbolic_geometry"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:multidimensional_scaling"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:hyperbolic_networks"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1402.1888">
    <title>[1402.1888] A Consistent Histogram Estimator for Exchangeable Graph Models</title>
    <dc:date>2014-02-11T21:33:42+00:00</dc:date>
    <link>http://arxiv.org/abs/1402.1888</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Exchangeable graph models (ExGM) subsume a number of popular network models. The mathematical object that characterizes an ExGM is termed a graphon. Finding scalable estimators of graphons, provably consistent, remains an open issue. In this paper, we propose a histogram estimator of a graphon that is provably consistent and numerically efficient. The proposed estimator is based on a sorting-and-smoothing (SAS) algorithm, which first sorts the empirical degree of a graph, then smooths the sorted graph using total variation minimization. The consistency of the SAS algorithm is proved by leveraging sparsity concepts from compressed sensing."]]></description>
<dc:subject>graph_limits network_data_analysis re:smoothing_adjacency_matrices scooped? have_read in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:4074499e7955/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_limits"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:scooped?"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:have_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1401.2906">
    <title>[1401.2906] An $L^p$ theory of sparse graph convergence I: limits, sparse random graph models, and power law distributions</title>
    <dc:date>2014-01-14T01:44:13+00:00</dc:date>
    <link>http://arxiv.org/abs/1401.2906</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We introduce and develop a theory of limits for sequences of sparse graphs based on Lp graphons, which generalizes both the existing L∞ theory of dense graph limits and its extension by Bollob\'as and Riordan to sparse graphs without dense spots. In doing so, we replace the no dense spots hypothesis with weaker assumptions, which allow us to analyze graphs with power law degree distributions. This gives the first broadly applicable limit theory for sparse graphs with unbounded average degrees. In this paper, we lay the foundations of the Lp theory of graphons, characterize convergence, and develop corresponding random graph models, while we prove the equivalence of several alternative metrics in a companion paper."]]></description>
<dc:subject>graph_limits re:smoothing_adjacency_matrices have_read mathematics in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:290898ff8194/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_limits"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:have_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1312.5306">
    <title>[1312.5306] Network histograms and universality of blockmodel approximation</title>
    <dc:date>2013-12-23T21:58:14+00:00</dc:date>
    <link>http://arxiv.org/abs/1312.5306</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["In this article we introduce the network histogram: a statistical summary of network interactions. A network histogram is obtained by fitting a stochastic blockmodel to a single observation of a network dataset. Blocks of edges play the role of histogram bins, and community sizes that of histogram bandwidths or bin sizes. Just as standard histograms allow for varying bandwidths, different blockmodel estimates can all be considered valid representations of an underlying probability model, subject to bandwidth constraints. We show that under these constraints, the mean integrated square error of the network histogram tends to zero as the network grows large, and we provide methods for optimal bandwidth selection--thus making the blockmodel a universal representation. With this insight, we discuss the interpretation of network communities in light of the fact that many different community assignments can all give an equally valid representation of the network. To demonstrate the fidelity-versus-interpretability tradeoff inherent in considering different numbers and sizes of communities, we show an example of detecting and describing new network community microstructure in political weblog data."]]></description>
<dc:subject>to:NB network_data_analysis re:smoothing_adjacency_matrices statistics to_read wolfe.patrick_j.</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:8307c25542dd/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:wolfe.patrick_j."/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1310.0532">
    <title>[1310.0532] Perfect Clustering for Stochastic Blockmodel Graphs via Adjacency Spectral Embedding</title>
    <dc:date>2013-11-22T17:38:38+00:00</dc:date>
    <link>http://arxiv.org/abs/1310.0532</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Vertex clustering in a stochastic blockmodel graph has wide applicability and has been the subject of extensive research. In this paper, we provide a short proof that the adjacency spectral embedding can be used to obtain perfect clustering for the stochastic blockmodel."]]></description>
<dc:subject>community_discovery spectral_clustering re:smoothing_adjacency_matrices have_read in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:ad5a25b047bb/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:community_discovery"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:spectral_clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:have_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1310.1495">
    <title>[1310.1495] Role of Normalization in Spectral Clustering for Stochastic Blockmodels</title>
    <dc:date>2013-11-22T16:30:03+00:00</dc:date>
    <link>http://arxiv.org/abs/1310.1495</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Spectral Clustering clusters elements using the top few eigenvectors of their (possibly normalized) similarity matrix. The quality of Spectral Clustering is closely tied to the convergence properties of these principal eigenvectors. This rate of convergence has been shown to be identical for both the normalized and unnormalized variants ([17]). However normalization for Spectral Clustering is the common practice ([16], [19]). Indeed, our experiments also show that normalization improves prediction accuracy. In this paper, for the popular Stochastic Blockmodel, we theoretically show that under spectral embedding, normalization shrinks the variance of points in a class by a constant fraction. As a byproduct of our work, we also obtain sharp deviation bounds of empirical principal eigenvalues of graphs generated from a Stochastic Blockmodel."]]></description>
<dc:subject>to_read spectral_clustering network_data_analysis community_discovery re:smoothing_adjacency_matrices sarkar.purnamrita heard_the_talk in_NB bickel.peter_j.</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:d7821e39aebc/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:spectral_clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:community_discovery"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:sarkar.purnamrita"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:heard_the_talk"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:bickel.peter_j."/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1311.1731">
    <title>[1311.1731] Stochastic blockmodel approximation of a graphon: Theory and consistent estimation</title>
    <dc:date>2013-11-14T04:49:44+00:00</dc:date>
    <link>http://arxiv.org/abs/1311.1731</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Non-parametric approaches for analyzing network data based on exchangeable graph models (ExGM) have recently gained interest. The key object that defines an ExGM is often referred to as a graphon. This non-parametric perspective on network modeling poses challenging questions on how to make inference on the graphon underlying observed network data. In this paper, we propose a computationally efficient procedure to estimate a graphon from a set of observed networks generated from it. This procedure is based on a stochastic blockmodel approximation (SBA) of the graphon. We show that, by approximating the graphon with a stochastic block model, the graphon can be consistently estimated, that is, the estimation error vanishes as the size of the graph approaches infinity."]]></description>
<dc:subject>graph_limits network_data_analysis community_discovery airoldi.edo to_read re:smoothing_adjacency_matrices in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:20ef7f1aa3dc/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_limits"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:community_discovery"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:airoldi.edo"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1310.6150">
    <title>[1310.6150] Bayesian Model Averaging of Stochastic Block Models to Estimate the Graphon Function and Motif Frequencies in a W-graph Model</title>
    <dc:date>2013-10-26T12:11:22+00:00</dc:date>
    <link>http://arxiv.org/abs/1310.6150</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["W-graph refers to a general class of random graph models that can be seen as a random graph limit. It is characterized by both its graphon function and its motif frequencies. The stochastic block model is a special case of W-graph where the graphon function is block-wise constant. In this paper, we propose a variational Bayes approach to estimate the W-graph as an average of stochastic block models with increasing number of blocks. We derive a variational Bayes algorithm and the corresponding variational weights for model averaging. In the same framework, we derive the variational posterior frequency of any motif. A simulation study and an illustration on a social network complete our work."]]></description>
<dc:subject>to_read graph_limits network_data_analysis statistics variational_inference re:smoothing_adjacency_matrices in_NB entableted</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:14a10bab56d2/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_limits"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:variational_inference"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:entableted"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1309.5936">
    <title>[1309.5936] Nonparametric graphon estimation</title>
    <dc:date>2013-09-24T13:51:18+00:00</dc:date>
    <link>http://arxiv.org/abs/1309.5936</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We propose a nonparametric framework for the analysis of networks, based on a natural limit object termed a graphon. We prove consistency of graphon estimation under general conditions, giving rates which include the important practical setting of sparse networks. Our results cover dense and sparse stochastic blockmodels with a growing number of classes, under model misspecification. We use profile likelihood methods, and connect our results to approximation theory, nonparametric function estimation, and the theory of graph limits."]]></description>
<dc:subject>graph_limits network_data_analysis community_discovery statistics wolfe.patrick_j. re:smoothing_adjacency_matrices please_dont_let_me_be_scooped have_read ok_not_quite_scooped in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:393ebb492cf3/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_limits"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:community_discovery"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:wolfe.patrick_j."/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:please_dont_let_me_be_scooped"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:have_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:ok_not_quite_scooped"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.stat.tamu.edu/~carroll/ftp/2002.papers.directory/berry_ruppert_carroll.pdf">
    <title>Bayesian Smoothing and Regression Splines for Measurement Error Problems</title>
    <dc:date>2013-09-24T03:19:02+00:00</dc:date>
    <link>http://www.stat.tamu.edu/~carroll/ftp/2002.papers.directory/berry_ruppert_carroll.pdf</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["In the presence of covariate measurement error, estimating a regression function nonparametrically is extremely dif􏰟 cult, the problem being related to deconvolution. Various frequentist approaches exist for this problem, but to date there has been no Bayesian treatment. In this article we describe Bayesian approaches to modeling a 􏰠 exible regression function when the predictor variable is measured with error. The regression function is modeled with smoothing splines and regression P-splines. Two methods are described for exploration of the posterior. The 􏰟 rst, called the iterative conditional modes ( ICM), is only partially Bayesian. ICM uses a componentwise maximization routine to 􏰟 nd the mode of the posterior. It also serves to create starting values for the second method, which is fully Bayesian and uses Markov chain Monte Carlo (MCMC) techniques to generate observations from the joint posterior distribution. Use of the MCMC approach has the advantage that interval estimates that directly model and adjust for the measurement error are easily calculated. We provide simulations with several nonlinear regression functions and provide an illustrative example. Our simulations indicate that the frequentist mean squared error properties of the fully Bayesian method are better than those of ICM and also of previously proposed frequentist methods, at least in the examples that we have studied."]]></description>
<dc:subject>to:NB regression nonparametrics splines statistics re:smoothing_adjacency_matrices to_read error-in-variables</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:c786a10ab7f6/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:regression"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:nonparametrics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:splines"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:error-in-variables"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://biomet.oxfordjournals.org/content/86/3/541.short">
    <title>Nonparametric regression in the presence of measurement error</title>
    <dc:date>2013-09-24T03:18:13+00:00</dc:date>
    <link>http://biomet.oxfordjournals.org/content/86/3/541.short</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["In many regression applications the independent variable is measured with error. When this happens, conventional parametric and nonparametric regression techniques are no longer valid. We consider two different approaches to nonparametric regression. The first uses the SIMEX, simulation-extrapolation, method and makes no assumption about the distribution of the unobserved error-prone predictor. For this approach we derive an asymptotic theory for kernel regression which has some surprising implications. Penalised regression splines are also considered for fixed number of known knots. The second approach assumes that the error-prone predictor has a distribution of a mixture of normals with an unknown number of components, and uses regression splines. Simulations illustrate the results."]]></description>
<dc:subject>regression nonparametrics re:smoothing_adjacency_matrices statistics have_read in_NB error-in-variables</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:e99cc74b36b3/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:regression"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:nonparametrics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:have_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:error-in-variables"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1306.6709">
    <title>[1306.6709] A Survey on Metric Learning for Feature Vectors and Structured Data</title>
    <dc:date>2013-07-01T18:56:59+00:00</dc:date>
    <link>http://arxiv.org/abs/1306.6709</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["The need for appropriate ways to measure the distance or similarity between data is ubiquitous in machine learning, pattern recognition and data mining, but handcrafting such good metrics for specific problems is generally difficult. This has led to the emergence of metric learning, which aims at automatically learning a metric from data and has attracted a lot of interest in machine learning and related fields for the past ten years. This survey paper proposes a systematic review of the literature in that area, highlighting the pros and cons of each approach. We pay particular attention to Mahalanobis distance learning, a well-studied and successful framework, but we also cover recent advances and trends of the field, such as similarity learning, nonlinear, local and semi-supervised methods, metric learning for histogram data and the derivation of generalization guarantees. This survey also addresses metric learning for structured data, in particular edit distance learning."]]></description>
<dc:subject>to:NB data_mining data_analysis structured_data statistics re:smoothing_adjacency_matrices</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:e3aecfca10ce/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:data_mining"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:structured_data"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1306.3524">
    <title>[1306.3524] Analysis of data in the form of graphs</title>
    <dc:date>2013-06-18T15:41:58+00:00</dc:date>
    <link>http://arxiv.org/abs/1306.3524</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We discuss the problem of extending data mining approaches to cases in which data points arise in the form of individual graphs. Being able to find the intrinsic low-dimensionality in ensembles of graphs can be useful in a variety of modeling contexts, especially when coarse-graining the detailed graph information is of interest. One of the main challenges in mining graph data is the definition of a suitable pairwise similarity metric in the space of graphs. We explore two practical solutions to solving this problem: one based on finding subgraph densities, and one using spectral information. The approach is illustrated on three test data sets (ensembles of graphs); two of these are obtained from standard graph generating algorithms, while the graphs in the third example are sampled as dynamic snapshots from an evolving network simulation."]]></description>
<dc:subject>data_mining graph_theory graph_limits spectral_methods network_data_analysis re:smoothing_adjacency_matrices re:network_differences in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:2f62f624c7c1/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:data_mining"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_limits"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:spectral_methods"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:network_differences"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1201.3861">
    <title>[1201.3861] Benjamini-Schramm convergence and the distribution of chromatic roots for sparse graphs</title>
    <dc:date>2013-04-23T13:22:52+00:00</dc:date>
    <link>http://arxiv.org/abs/1201.3861</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We define the chromatic measure of a finite simple graph as the uniform distribution on its chromatic roots. We show that for a Benjamini-Schramm convergent sequence of finite graphs, the chromatic measures converge in holomorphic moments. 
"As a corollary, for a convergent sequence of finite graphs, we prove that the normalized log of the chromatic polynomial converges to an analytic function outside a bounded disc. This generalizes a recent result of Borgs, Chayes, Kahn and Lov\'asz, who proved convergence at large enough positive integers and answers a question of Borgs. 
"Our methods also lead to explicit estimates on the number of proper colorings of graphs with large girth."]]></description>
<dc:subject>graph_theory graph_limits re:smoothing_adjacency_matrices via:david.choi in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:df8a798a23dc/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_limits"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:via:david.choi"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1302.0870">
    <title>[1302.0870] Centrality-constrained graph embedding</title>
    <dc:date>2013-03-06T14:49:52+00:00</dc:date>
    <link>http://arxiv.org/abs/1302.0870</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Visual rendering of graphs is a key task in the mapping of complex network data. Although most graph drawing algorithms emphasize aesthetic appeal, certain applications such as travel-time maps place more importance on visualization of structural network properties. The present paper advocates a graph embedding approach with centrality considerations to comply with node hierarchy. The problem is formulated as one of constrained multi-dimensional scaling (MDS), and it is solved via block coordinate descent iterations with successive approximations and guaranteed convergence to a KKT point. In addition, a regularization term enforcing graph smoothness is incorporated with the goal of reducing edge crossings. Experimental results demonstrate that the algorithm converges, and can be used to efficiently embed large graphs on the order of thousands of nodes."]]></description>
<dc:subject>to:NB network_data_analysis graph_theory visual_display_of_quantitative_information re:6dfb re:smoothing_adjacency_matrices</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:722674bfa1b9/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:visual_display_of_quantitative_information"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:6dfb"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.ams.org/bookstore-getitem/item=COLL-60">
    <title>Large Networks and Graph Limits</title>
    <dc:date>2013-03-05T22:34:42+00:00</dc:date>
    <link>http://www.ams.org/bookstore-getitem/item=COLL-60</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Recently, it became apparent that a large number of the most interesting structures and phenomena of the world can be described by networks. Developing a mathematical theory of very large networks is an important challenge. This book describes one recent approach to this theory, the limit theory of graphs, which has emerged over the last decade. The theory has rich connections with other approaches to the study of large networks, such as "property testing" in computer science and regularity partition in graph theory. It has several applications in extremal graph theory, including the exact formulations and partial answers to very general questions, such as which problems in extremal graph theory are decidable. It also has less obvious connections with other parts of mathematics (classical and non-classical, like probability theory, measure theory, tensor algebras, and semidefinite optimization).
"This book explains many of these connections, first at an informal level to emphasize the need to apply more advanced mathematical methods, and then gives an exact development of the algebraic theory of graph homomorphisms and of the analytic theory of graph limits."]]></description>
<dc:subject>graph_theory graph_limits lovasz.laszlo re:smoothing_adjacency_matrices re:network_differences books:recommended have_read books:owned in_NB via:arinaldo</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:abc06ba2e83d/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_limits"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:lovasz.laszlo"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:network_differences"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:books:recommended"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:have_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:books:owned"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:via:arinaldo"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1302.4615">
    <title>[1302.4615] Convergent sequences of sparse graphs: A large deviations approach</title>
    <dc:date>2013-02-21T15:06:15+00:00</dc:date>
    <link>http://arxiv.org/abs/1302.4615</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["In this paper we introduce a new notion of convergence of sparse graphs which we call Large Deviations or LD-convergence and which is based on the theory of large deviations. The notion is introduced by "decorating" the nodes of the graph with random uniform i.i.d. weights and constructing random measures on $[0,1]$ and $[0,1]^2$ based on the decoration of nodes and edges. A graph sequence is defined to be converging if the corresponding sequence of random measures satisfies the Large Deviations Principle with respect to the topology of weak convergence on bounded measures on $[0,1]^d, d=1,2$. We then establish that LD-convergence implies several previous notions of convergence, namely so-called right-convergence, left-convergence, and partition-convergence. The corresponding large deviation rate function can be interpreted as the limit object of the sparse graph sequence. In particular, we can express the limiting free energies in terms of this limit object."

- Picture me jumping up and down excitedly.]]></description>
<dc:subject>graph_limits graph_theory stochastic_processes large_deviations re:smoothing_adjacency_matrices re:network_differences chayes.jennifer borgs.christian re:almost_none in_NB have_read</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:d35479322ce9/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_limits"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:stochastic_processes"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:large_deviations"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:network_differences"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:chayes.jennifer"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:borgs.christian"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:almost_none"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:have_read"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1010.4202">
    <title>[1010.4202] M&quot;{o}bius deconvolution on the hyperbolic plane with application to impedance density estimation</title>
    <dc:date>2013-02-18T20:10:22+00:00</dc:date>
    <link>http://arxiv.org/abs/1010.4202</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["In this paper we consider a novel statistical inverse problem on the Poincar'{e}, or Lobachevsky, upper (complex) half plane. Here the Riemannian structure is hyperbolic and a transitive group action comes from the space of $2times2$ real matrices of determinant one via M"{o}bius transformations. Our approach is based on a deconvolution technique which relies on the Helgason--Fourier calculus adapted to this hyperbolic space. This gives a minimax nonparametric density estimator of a hyperbolic density that is corrupted by a random M"{o}bius transform. A motivation for this work comes from the reconstruction of impedances of capacitors where the above scenario on the Poincar'{e} plane exactly describes the physical system that is of statistical interest."]]></description>
<dc:subject>have_read density_estimation deconvolution statistics hyperbolic_geometry re:smoothing_adjacency_matrices fourier_analysis via:dena in_NB re:hyperbolic_networks re:network_differences</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:5429cdc9a22b/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:have_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:density_estimation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:deconvolution"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:hyperbolic_geometry"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:fourier_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:via:dena"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:hyperbolic_networks"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:network_differences"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://books.nips.cc/papers/files/nips25/NIPS2012_0487.pdf">
    <title>Random function priors for exchangeable arrays with applications to graphs and relational data</title>
    <dc:date>2013-02-18T02:42:17+00:00</dc:date>
    <link>http://books.nips.cc/papers/files/nips25/NIPS2012_0487.pdf</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["A fundamental problem in the analysis of structured relational data like graphs, networks, databases, and matrices is to extract a summary of the common structure underlying relations between individual entities. Relational data are typically encoded in the form of arrays; invariance to the ordering of rows and columns corresponds to exchangeable arrays. Results in probability theory due to Aldous, Hoover and Kallenberg show that exchangeable arrays can be represented in terms of a random measurable function which constitutes the natural model parameter in a Bayesian model. We obtain a flexible yet simple Bayesian nonparametric model by placing a Gaussian process prior on the parameter function. Efficient inference utilises elliptical slice sampling combined with a random sparse approximation to the Gaussian process. We demonstrate applications of the model to network data and clarify its relation to models in the literature, several of which emerge as special cases."]]></description>
<dc:subject>network_data_analysis nonparametrics re:smoothing_adjacency_matrices statistics ghahramani.zoubin in_NB have_read orbanz.peter</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:7a9ac3c0c370/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:nonparametrics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:ghahramani.zoubin"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:have_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:orbanz.peter"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://pre.aps.org/abstract/PRE/v68/i3/e036112">
    <title>Phys. Rev. E 68, 036112 (2003): Class of correlated random networks with hidden variables</title>
    <dc:date>2013-01-30T23:02:49+00:00</dc:date>
    <link>http://pre.aps.org/abstract/PRE/v68/i3/e036112</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We study a class of models of correlated random networks in which vertices are characterized by hidden variables controlling the establishment of edges between pairs of vertices. We find analytical expressions for the main topological properties of these models as a function of the distribution of hidden variables and the probability of connecting vertices. The expressions obtained are checked by means of numerical simulations in a particular example. The general model is extended to describe a practical algorithm to generate random networks with an a priori specified correlation structure. We also present an extension of the class, to map nonequilibrium growing networks to networks with hidden variables that represent the time at which each vertex was introduced in the system."]]></description>
<dc:subject>networks graph_limits re:smoothing_adjacency_matrices re:network_differences in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:b220f6ceacb3/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:networks"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_limits"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:network_differences"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1212.4093">
    <title>[1212.4093] Co-clustering separately exchangeable network data</title>
    <dc:date>2012-12-18T14:05:26+00:00</dc:date>
    <link>http://arxiv.org/abs/1212.4093</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We analyze the co-clustering problem of partitioning a bipartite graph or binary array into subsets, under the assumption only that the data are generated by a nonparametric process satisfying the condition of separate exchangeability. We provide oracle inequalities with rate of convergence n^(-1/4) corresponding to profile likelihood maximization and mean-square error minimization, and show that the stochastic co-blockmodel can be interpreted in this setting as an optimal piecewise-constant approximation to the generative nonparametric model. We also show for large sample sizes that detection of co-clusters in such data indicates with high probability the existence of co-clusters of similar proportion and connectivity in the generative process."]]></description>
<dc:subject>have_read re:smoothing_adjacency_matrices kith_and_kin graph_limits network_data_analysis clustering statistics nonparametrics in_NB choi.david_s. wolfe.patrick_j.</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:4e9420270634/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:have_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:kith_and_kin"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_limits"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:nonparametrics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:choi.david_s."/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:wolfe.patrick_j."/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.stat.washington.edu/people/dcpj/_static/DirectedEmbedding.pdf">
    <title>Directed Graph Embedding: an Algorithm based on Continuous Limits of Laplacian-type Operators</title>
    <dc:date>2012-09-04T17:29:11+00:00</dc:date>
    <link>http://www.stat.washington.edu/people/dcpj/_static/DirectedEmbedding.pdf</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["This paper considers the problem of embedding directed graphs in Euclidean space while retaining directional information. We model the observed graph as a sample from a manifold endowed with a vector field, and we design an algo- rithm that separates and recovers the features of this process: the geometry of the manifold, the data density and the vector field. The algorithm is motivated by our analysis of Laplacian-type operators and their continuous limit as generators of diffusions on a manifold. We illustrate the recovery algorithm on both artificially constructed and real data."]]></description>
<dc:subject>graph_theory manifold_learning machine_learning statistics re:smoothing_adjacency_matrices network_data_analysis meila.marina markov_models</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:9efcc3d13858/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:manifold_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:machine_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:meila.marina"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:markov_models"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/0902.0132">
    <title>[0902.0132] Very large graphs</title>
    <dc:date>2012-08-21T03:00:02+00:00</dc:date>
    <link>http://arxiv.org/abs/0902.0132</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["In the last decade it became apparent that a large number of the most interesting structures and phenomena of the world can be described by networks: separable elements, with connections (or interactions) between certain pairs of them. 
"These huge networks pose exciting challenges for the mathematician. Graph Theory (the mathematical theory of networks) faces novel, unconventional problems: these very large networks (like the Internet) are never completely known, in most cases they are not even well defined. Data about them can be collected only by indirect means like random local sampling. 
"Dense networks (in which a node is adjacent to a positive percent of others nodes) and sparse networks (in which a node has a bounded number of neighbors) show very different behavior. From a practical point of view, sparse networks are more important, but at present we have more complete theoretical results for dense networks. The paper surveys relations with probability, algebra, extrema graph theory, and analysis."]]></description>
<dc:subject>graph_limits graph_theory re:smoothing_adjacency_matrices network_data_analysis via:shivak lovasz.laszlo in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:94ef34065660/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_limits"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:via:shivak"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:lovasz.laszlo"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/math.CO/0408173">
    <title>[math/0408173] Limits of dense graph sequences</title>
    <dc:date>2012-08-14T02:08:10+00:00</dc:date>
    <link>http://arxiv.org/abs/math.CO/0408173</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We show that if a sequence of dense graphs has the property that for every fixed graph F, the density of copies of F in these graphs tends to a limit, then there is a natural ``limit object'', namely a symmetric measurable 2-variable function on [0,1]. This limit object determines all the limits of subgraph densities. We also show that the graph parameters obtained as limits of subgraph densities can be characterized by ``reflection positivity'', semidefiniteness of an associated matrix. Conversely, every such function arises as a limit object. Along the lines we introduce a rather general model of random graphs, which seems to be interesting on its own right."

- Note theorem 2.5 in particular.  Why is the concentration rate proportional to the number of nodes and not edges?

--- ETA several years later: Because each node, while it adds n observations, also adds 1 new parameter.]]></description>
<dc:subject>in_NB have_read graph_theory graph_limits re:smoothing_adjacency_matrices</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:4a978aef6824/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:have_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_limits"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1206.2380">
    <title>[1206.2380] The Highest Dimensional Stochastic Blockmodel with a Regularized Estimator</title>
    <dc:date>2012-06-23T15:12:43+00:00</dc:date>
    <link>http://arxiv.org/abs/1206.2380</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["This paper advances the high dimensional frontier for network clustering. In the high dimensional Stochastic Blockmodel for a random network, the number of clusters (or blocks) K grows with the number of nodes N. Previous authors have studied the statistical estimation performance of spectral clustering and the maximum likelihood estimator under the high dimensional model. These authors do not allow K to grow faster than N^{1/2}. We study a model where, ignoring log terms, K can grow proportionally to N. Since the number of clusters must be smaller than the number of nodes, no reasonable model allows K to grow faster; thus, our asymptotic results are the "highest" dimensional. To push the asymptotic setting to this extreme, we develop a regularized maximum likelihood estimator. We prove that, under certain conditions, the proportion of nodes that the regularized estimator misclusters converges to zero. 
"This is the first paper to explicitly introduce and demonstrate the advantages of statistical regularization for network analysis. Empirical observation in physical anthropology and an in depth study of massive empirical networks by motivate both our asymptotic setting and regularized estimator."]]></description>
<dc:subject>network_data_analysis community_discovery re:network_differences re:smoothing_adjacency_matrices to_read statistics in_NB color_me_skeptical</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:fad92655888c/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:community_discovery"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:network_differences"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:color_me_skeptical"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1203.2269">
    <title>Graphlets: a Spectral Perspective for Graph Limits</title>
    <dc:date>2012-04-26T18:53:59+00:00</dc:date>
    <link>http://arxiv.org/abs/1203.2269</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Graphlets give a spectral approach to graph limits for general graph sequences in a framework that unifies previous disparate approaches for dealing with dense graphs and sparse graphs. We will show that the con- vergence to graphlets under the appropriate spectral distance is equivalent to the convergence using the (normalized) cut distance. We then examine the geometry of graphlets, illustrated by examples of several families of graphlets and, in particular, graphlets with low ranks. We further dis- cuss a number of usages of graphlets, including universal scalable bases, universal embeddings vis heat kernels and the preservation of Cheeger cuts."

ETA: This is so not an easy read.  I like what I understand, but I definitely have to make another attack on it.]]></description>
<dc:subject>to_read graph_theory graph_limits re:smoothing_adjacency_matrices re:network_differences chung.fan graph_spectra via:arinaldo in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:9168a6e97916/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_limits"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:network_differences"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:chung.fan"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_spectra"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:via:arinaldo"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1201.5871">
    <title>[1201.5871] Null models for network data</title>
    <dc:date>2012-04-20T19:19:33+00:00</dc:date>
    <link>http://arxiv.org/abs/1201.5871</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["The analysis of datasets taking the form of simple, undirected graphs continues to gain in importance across a variety of disciplines. Two choices of null model, the logistic-linear model and the implicit log-linear model, have come into common use for analyzing such network data, in part because each accounts for the heterogeneity of network node degrees typically observed in practice. Here we show how these both may be viewed as instances of a broader class of null models, with the property that all members of this class give rise to essentially the same likelihood-based estimates of link probabilities in sparse graph regimes. This facilitates likelihood-based computation and inference, and enables practitioners to choose the most appropriate null model from this family based on application context. Comparative model fits for a variety of network datasets demonstrate the practical implications of our results."]]></description>
<dc:subject>network_data_analysis have_read statistics estimation approximation re:smoothing_adjacency_matrices in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:dad6c5c2ca1e/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:have_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:estimation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1202.3123">
    <title>[1202.3123] Right-convergence of sparse random graphs</title>
    <dc:date>2012-02-15T13:27:16+00:00</dc:date>
    <link>http://arxiv.org/abs/1202.3123</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["The paper is devoted to the problem of establishing right-convergence of sparse random graphs. This concerns the convergence of the logarithm of number of homomorphisms from graphs or hyper-graphs $G_N, Nge 1$ to some target graph $W$. The theory of dense graph convergence, including random dense graphs, is now well understood, but its counterpart for sparse random graphs presents some fundamental difficulties. Phrased in the statistical physics terminology, the issue is the existence of the log-partition function limits, also known as free energy limits, appropriately normalized for the Gibbs distribution associated with $W$. In this paper we prove that the sequence of sparse ER graphs is right-converging when the tensor product associated with the target graph $W$ satisfies certain convexity property. We treat the case of discrete and continuous target graphs $W$. The latter case allows us to prove a special case of Talagrand's recent conjecture (more accurately stated as level III Research Problem 6.7.2 in his recent book), concerning the existence of the limit of the measure of a set obtained from $R^N$ by intersecting it with linearly in $N$ many subsets, generated according to some common probability law. 
Our proof is based on the interpolation technique, introduced first by Guerra and Toninelli and developed further in a series of papers. Specifically, Bayati et al establish the right-convergence property for Erdos-Renyi graphs for some special cases of $W$. In this paper most of the results in this paper follow as a special case of our main theorem."]]></description>
<dc:subject>graph_theory graph_limits re:smoothing_adjacency_matrices in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:b8d6fac13492/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_limits"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://projecteuclid.org/DPubS?service=UI&amp;version=1.0&amp;verb=Display&amp;handle=euclid.aos/1321020525">
    <title>Bickel , Chen , Levina : The method of moments and degree distributions for network models</title>
    <dc:date>2011-11-11T15:08:22+00:00</dc:date>
    <link>http://projecteuclid.org/DPubS?service=UI&amp;version=1.0&amp;verb=Display&amp;handle=euclid.aos/1321020525</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Probability models on graphs are becoming increasingly important in many applications, but statistical tools for fitting such models are not yet well developed. Here we propose a general method of moments approach that can be used to fit a large class of probability models through empirical counts of certain patterns in a graph. We establish some general asymptotic properties of empirical graph moments and prove consistency of the estimates as the graph size grows for all ranges of the average degree including Omega(1). Additional results are obtained for the important special case of degree distributions."

After reading this, I note that they do not go through even one example of actually estimating anything.  I think this is because the inversion from moments to graphons, while mathematically well-defined, is hellish to calculate (and probably very numerically unstable).]]></description>
<dc:subject>network_data_analysis statistics estimation levina.elizaveta re:smoothing_adjacency_matrices in_NB have_read bickel.peter_j.</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:4ae4ed83137a/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:estimation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:levina.elizaveta"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:have_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:bickel.peter_j."/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://ergodicity.net/2011/10/30/banff-blog/">
    <title>Banff blog « An Ergodic Walk</title>
    <dc:date>2011-10-30T20:31:58+00:00</dc:date>
    <link>http://ergodicity.net/2011/10/30/banff-blog/</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA[Sounds delightful (and Banff is beautiful).
]]></description>
<dc:subject>conferences statistics learning_theory statistical_inference_for_stochastic_processes track_down_references markov_models network_data_analysis estimation van_handel.ramon nonparametrics re:smoothing_adjacency_matrices information_theory</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:b9e4e121c609/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:conferences"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistical_inference_for_stochastic_processes"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:track_down_references"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:markov_models"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:estimation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:van_handel.ramon"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:nonparametrics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:information_theory"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1110.5383">
    <title>[1110.5383] Quilting Stochastic Kronecker Product Graphs to Generate Multiplicative Attribute Graphs</title>
    <dc:date>2011-10-26T15:49:01+00:00</dc:date>
    <link>http://arxiv.org/abs/1110.5383</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We describe the first sub-quadratic sampling algorithm for the Multiplicative Attribute Graph Model (MAGM) of Kim and Leskovec (2010). We exploit the close connection between MAGM and the Kronecker Product Graph Model (KPGM) of Leskovec et al. (2010), and show that to sample a graph from a MAGM it suffices to sample small number of KPGM graphs and emph{quilt} them together. Under mild technical conditions our algorithm runs in $O((log_2(n))^3 |E|)$ time, where $n$ is the number of nodes and $|E|$ is the number of edges in the sampled graph. We demonstrate the scalability of our algorithm via extensive empirical evaluation; we can sample a MAGM graph with 8 million nodes and 20 billion edges in under 6 hours."]]></description>
<dc:subject>to_read network_data_analysis in_NB re:smoothing_adjacency_matrices</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:3bfa0ef221dd/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://projecteuclid.org/DPubS?service=UI&amp;version=1.0&amp;verb=Display&amp;handle=euclid.ejs/1319028571">
    <title>Orbanz : Projective limit random probabilities on Polish spaces</title>
    <dc:date>2011-10-19T15:36:36+00:00</dc:date>
    <link>http://projecteuclid.org/DPubS?service=UI&amp;version=1.0&amp;verb=Display&amp;handle=euclid.ejs/1319028571</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["A pivotal problem in Bayesian nonparametrics is the construction of prior distributions on the space M(V) of probability measures on a given domain V. In principle, such distributions on the infinite-dimensional space M(V) can be constructed from their finite-dimensional marginals—the most prominent example being the construction of the Dirichlet process from finite-dimensional Dirichlet distributions. This approach is both intuitive and applicable to the construction of arbitrary distributions on M(V), but also hamstrung by a number of technical difficulties. We show how these difficulties can be resolved if the domain V is a Polish topological space, and give a representation theorem directly applicable to the construction of any probability distribution on M(V) whose first moment measure is well-defined. The proof draws on a projective limit theorem of Bochner, and on properties of set functions on Polish spaces to establish countable additivity of the resulting random probabilities."]]></description>
<dc:subject>probability stochastic_processes measure_theory orbanz.peter to_read re:smoothing_adjacency_matrices high-dimensional_probability in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:c949e23cf015/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:probability"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:stochastic_processes"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:measure_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:orbanz.peter"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:smoothing_adjacency_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:high-dimensional_probability"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
</rdf:RDF>