<?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://link.springer.com/article/10.1007/s10955-026-03647-6"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/math/0504472"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2512.02208"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2212.01987"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2503.18823"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2310.12397"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2305.12470"/>
	<rdf:li rdf:resource="https://www.pnas.org/doi/10.1073/pnas.2215752120"/>
	<rdf:li rdf:resource="https://www.cambridge.org/core/books/mathematics-of-finite-networks/E8CB5F1654ABC535D5A6A191BCF157F1#fndtn-information"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2202.01563"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2203.07230"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2201.04888"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2103.04668"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2105.03122"/>
	<rdf:li rdf:resource="https://www.annualreviews.org/doi/abs/10.1146/annurev-control-061820-083817"/>
	<rdf:li rdf:resource="https://www.annualreviews.org/doi/abs/10.1146/annurev-control-061520-010504"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1411.0650"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2103.11818"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2102.02653"/>
	<rdf:li rdf:resource="https://journals.aps.org/pre/abstract/10.1103/PhysRevE.103.012309"/>
	<rdf:li rdf:resource="https://nowpublishers.com/article/Details/MAL-078-2"/>
	<rdf:li rdf:resource="https://nowpublishers.com/article/Details/MAL-078-1"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2101.03618"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2012.12309"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1705.06815"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1906.08806"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2012.05129"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1910.09483"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1908.08572"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1902.03002"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1908.06057"/>
	<rdf:li rdf:resource="https://www.cambridge.org/core/books/inequalities-for-graph-eigenvalues/0047197D65BB927AAC906784CC7F3774#fndtn-information"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1705.02801"/>
	<rdf:li rdf:resource="https://mitpress.mit.edu/books/mathematics-big-data"/>
	<rdf:li rdf:resource="http://www.cambridge.org/us/academic/subjects/mathematics/discrete-mathematics-information-theory-and-coding/eigenvalues-multiplicities-and-graphs?format=HB&amp;WT.mc_id=Cambridge%2BTracts%2Bin%2BMathematics%2BCluster#OFbA1DJep21QxzhX.97"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1311.6425"/>
	<rdf:li rdf:resource="https://cs.brown.edu/~rt/gdhandbook/"/>
	<rdf:li rdf:resource="http://www.cambridge.org/us/academic/subjects/mathematics/discrete-mathematics-information-theory-and-coding/random-graphs-geometry-and-asymptotic-structure?format=HB&amp;isbn=9781107136571"/>
	<rdf:li rdf:resource="http://link.springer.com/article/10.1007/BF01200757"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1506.00669"/>
	<rdf:li rdf:resource="http://www.pnas.org/content/112/10/2942.abstract.html"/>
	<rdf:li rdf:resource="http://press.princeton.edu/titles/10314.html"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1405.3133"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1411.1546"/>
	<rdf:li rdf:resource="http://link.springer.com/article/10.1007/s11009-012-9311-x"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1407.0224"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1405.1440"/>
	<rdf:li rdf:resource="http://dl.acm.org/citation.cfm?doid=2435209.2435212"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1403.3448"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1403.0598"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1312.1970"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1312.5179"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1311.7656"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1307.7729"/>
	<rdf:li rdf:resource="http://www.win.tue.nl/~rhofstad/NotesRGCN.html"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1307.2302"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1306.3524"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1306.3401"/>
	<rdf:li rdf:resource="http://www.jstor.org/stable/10.1086/670300"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1305.3146"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1304.7528"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1201.3861"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1304.1548"/>
	<rdf:li rdf:resource="http://www.tandfonline.com/doi/abs/10.1080/15427951.2010.557277"/>
	<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://hal.archives-ouvertes.fr/inria-00630774/"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1302.4615"/>
	<rdf:li rdf:resource="http://www.cambridge.org/us/knowledge/isbn/item6958599/?site_locale=en_US"/>
	<rdf:li rdf:resource="http://pre.aps.org/abstract/PRE/v87/i1/e012803"/>
      </rdf:Seq>
    </items>
  </channel><item rdf:about="https://link.springer.com/article/10.1007/s10955-026-03647-6">
    <title>Large Deviations for Subgraphs in Inhomogeneous Random Graphs | Journal of Statistical Physics | Springer Nature Link</title>
    <dc:date>2026-06-25T18:24:18+00:00</dc:date>
    <link>https://link.springer.com/article/10.1007/s10955-026-03647-6</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Inhomogeneous random graphs are fundamental models for real-world networks, where prescribed degrees are imposed as soft constraints. A common assumption in such models is that the degree distribution follows a power-law, capturing the heavy-tailed nature observed in many contexts. While various graph functionals have been studied in this setting, inhomogeneity makes their analysis significantly more challenging. Here, we investigate the large deviations of subgraph counts in inhomogeneous random graphs. Rare events concerning these functionals translate into quantifying the probability that extremely large hubs appear in the graph. This can be achieved by defining a specific optimization problem that captures the most likely way to generate numerous additional subgraphs. When the expected number of subgraphs is sublinear in the graph size, polynomially large deviations are possible, and in this case, we can derive sharp results on clique counts."]]></description>
<dc:subject>to:NB large_deviations graph_theory graph_limits</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:b8c7a77f8a95/</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:large_deviations"/>
	<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:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/math/0504472">
    <title>[math/0504472] Szemerédi's regularity lemma revisited</title>
    <dc:date>2026-04-08T02:30:02+00:00</dc:date>
    <link>https://arxiv.org/abs/math/0504472</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Szemerédi's regularity lemma is a basic tool in graph theory, and also plays an important role in additive combinatorics, most notably in proving Szemerédi's theorem on arithmetic progressions . In this note we revisit this lemma from the perspective of probability theory and information theory instead of graph theory, and observe a variant of this lemma which introduces a new parameter F. This stronger version of the regularity lemma was iterated in a recent paper of the author to reprove the analogous regularity lemma for hypergraphs."

--- Re last tag, I ought to try to find time to think about this as a form of (approximate) statistical sufficiency, and/or the information bottleneck.]]></description>
<dc:subject>have_read tao.terence graph_theory information_theory probability coarse_graining sufficiency in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:b71042d4baec/</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:tao.terence"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:information_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:probability"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:coarse_graining"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:sufficiency"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2512.02208">
    <title>[2512.02208] Projective limits of probabilistic symmetries and their applications to random graph limits</title>
    <dc:date>2025-12-06T14:27:58+00:00</dc:date>
    <link>https://arxiv.org/abs/2512.02208</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We couple projective limits of probability measures to direct limits of their symmetry groups. We show that the direct limit group is the group of symmetries of the projective limit probability measure. If projective systems of probability measures represent point processes in increasingly larger finite regions of the same infinite space, then we show that under some additional niceness and consistency assumptions, an extension of the direct limit group is the symmetry group of the projective limit point process in the whole infinite space. The application of these results to random graph limits provides ``shortest paths'' to graphons and graphexes as it recovers these random graph limits as trivial corollaries. Another application example encompasses a broad class of limits of random graphs with bounded average degrees. This class includes a representative collection of paradigmatic random graph models that have attracted significant research attention in diverse areas of science. Our approach thus provides a general unified framework to study limits of very different types of random graphs."]]></description>
<dc:subject>to:NB graph_theory graph_limits point_processes symmetry to_read krioukov.dmitri</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:6f35f1d08be2/</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_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_limits"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:point_processes"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:symmetry"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:krioukov.dmitri"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2212.01987">
    <title>[2212.01987] Fractal dimensions for Iterated Graph Systems</title>
    <dc:date>2025-12-03T20:39:06+00:00</dc:date>
    <link>https://arxiv.org/abs/2212.01987</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Building upon [1], this study aims to introduce fractal geometry into graph theory, and to establish a potential theoretical foundation for complex networks. Specifically, we employ the method of substitution to create and explore fractal-like graphs, termed deterministic or random iterated graph systems. While the concept of substitution is commonplace in fractal geometry and dynamical systems, its analysis in the context of graph theory remains a nascent field.
"By delving into the properties of these systems, including diameter and distal, we derive two primary outcomes. Firstly, within the deterministic iterated graph systems, we establish that the Minkowski dimension and Hausdorff dimension align analytically through explicit formulae. Secondly, in the case of random iterated graph systems, we demonstrate that almost every graph limit exhibits identical Minkowski and Hausdorff dimensions numerically by their Lyapunov exponents.
"The exploration of iterated graph systems holds the potential to unveil novel directions. These findings not only, mathematically, contribute to our understanding of the interplay between fractals and graphs, but also, physically, suggest promising avenues for applications for complex networks."]]></description>
<dc:subject>to:NB fractals networks graph_theory re:fractal_network_asymptotics to_read scooped? via:vaguery</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:0d244921ef96/</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:fractals"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:networks"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:fractal_network_asymptotics"/>
	<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:via:vaguery"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2503.18823">
    <title>[2503.18823] Coarse-graining Directed Networks with Ergodic Sets Preserving Diffusive Dynamics</title>
    <dc:date>2025-03-31T23:42:53+00:00</dc:date>
    <link>https://arxiv.org/abs/2503.18823</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["In this paper, we introduce ergodic sets, subsets of nodes of the networks that are dynamically disjoint from the rest of the network (i.e. that can never be reached or left following to the network dynamics). We connect their definition to purely structural considerations of the network and study some of their basic properties. We study numerically the presence of such structures in a number of synthetic network models and in classes of networks from a variety of real-world applications, and we use them to present a compression algorithm that preserve the random walk diffusive dynamics of the original network."

--- "Can never be left" would not be so interesting, in fact it'd be pretty classical.  "Can never be reached" will either make this interesting or trivial.]]></description>
<dc:subject>to:NB networks graph_theory</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:b70e1137cb6c/</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:networks"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_theory"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2310.12397">
    <title>[2310.12397] GPT-4 Doesn't Know It's Wrong: An Analysis of Iterative Prompting for Reasoning Problems</title>
    <dc:date>2023-11-16T02:56:12+00:00</dc:date>
    <link>https://arxiv.org/abs/2310.12397</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["There has been considerable divergence of opinion on the reasoning abilities of Large Language Models (LLMs). While the initial optimism that reasoning might emerge automatically with scale has been tempered thanks to a slew of counterexamples, a wide spread belief in their iterative self-critique capabilities persists. In this paper, we set out to systematically investigate the effectiveness of iterative prompting of LLMs in the context of Graph Coloring, a canonical NP-complete reasoning problem that is related to propositional satisfiability as well as practical problems like scheduling and allocation. We present a principled empirical study of the performance of GPT4 in solving graph coloring instances or verifying the correctness of candidate colorings. In iterative modes, we experiment with the model critiquing its own answers and an external correct reasoner verifying proposed solutions. In both cases, we analyze whether the content of the criticisms actually affects bottom line performance. The study seems to indicate that (i) LLMs are bad at solving graph coloring instances (ii) they are no better at verifying a solution--and thus are not effective in iterative modes with LLMs critiquing LLM-generated solutions (iii) the correctness and content of the criticisms--whether by LLMs or external solvers--seems largely irrelevant to the performance of iterative prompting. We show that the observed increase in effectiveness is largely due to the correct solution being fortuitously present in the top-k completions of the prompt (and being recognized as such by an external verifier). Our results thus call into question claims about the self-critiquing capabilities of state of the art LLMs."]]></description>
<dc:subject>large_language_models_(so_called) artificial_intelligence graph_theory in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:f2b855eb672f/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:large_language_models_(so_called)"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:artificial_intelligence"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2305.12470">
    <title>[2305.12470] Quasi-Monte Carlo Graph Random Features</title>
    <dc:date>2023-05-28T13:45:37+00:00</dc:date>
    <link>https://arxiv.org/abs/2305.12470</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We present a novel mechanism to improve the accuracy of the recently-introduced class of graph random features (GRFs). Our method induces negative correlations between the lengths of the algorithm's random walks by imposing antithetic termination: a procedure to sample more diverse random walks which may be of independent interest. It has a trivial drop-in implementation. We derive strong theoretical guarantees on the properties of these quasi-Monte Carlo GRFs (q-GRFs), proving that they yield lower-variance estimators of the 2-regularised Laplacian kernel under mild conditions. Remarkably, our results hold for any graph topology. We demonstrate empirical accuracy improvements on a variety of tasks including a new practical application: time-efficient approximation of the graph diffusion process. To our knowledge, q-GRFs constitute the first rigorously studied quasi-Monte Carlo scheme for kernels defined on combinatorial objects, inviting new research on correlations between graph random walks."]]></description>
<dc:subject>random_features network_data_analysis monte_carlo graph_theory to_read re:codename:catherine_wheel in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:98485ad59efc/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:random_features"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:monte_carlo"/>
	<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:codename:catherine_wheel"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://www.pnas.org/doi/10.1073/pnas.2215752120">
    <title>Strong connectivity in real directed networks | PNAS</title>
    <dc:date>2023-03-21T15:38:23+00:00</dc:date>
    <link>https://www.pnas.org/doi/10.1073/pnas.2215752120</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["In many real, directed networks, the strongly connected component of nodes which are mutually reachable is very small. This does not fit with current theory, based on random graphs, according to which strong connectivity depends on mean degree and degree–degree correlations. And it has important implications for other properties of real networks and the dynamical behavior of many complex systems. We find that strong connectivity depends crucially on the extent to which the network has an overall direction or hierarchical ordering—a property measured by trophic coherence. Using percolation theory, we find the critical point separating weakly and strongly connected regimes and confirm our results on many real-world networks, including ecological, neural, trade, and social networks. We show that the connectivity structure can be disrupted with minimal effort by a targeted attack on edges which run counter to the overall direction. This means that many dynamical processes on networks can depend significantly on a small fraction of edges."]]></description>
<dc:subject>to:NB percolation_theory graph_theory networks</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:4e85d56f5328/</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:percolation_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:networks"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://www.cambridge.org/core/books/mathematics-of-finite-networks/E8CB5F1654ABC535D5A6A191BCF157F1#fndtn-information">
    <title>The Mathematics of Finite Networks</title>
    <dc:date>2022-07-02T13:41:39+00:00</dc:date>
    <link>https://www.cambridge.org/core/books/mathematics-of-finite-networks/E8CB5F1654ABC535D5A6A191BCF157F1#fndtn-information</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Since the early eighteenth century, the theory of networks and graphs has matured into an indispensable tool for describing countless real-world phenomena. However, the study of large-scale features of a network often requires unrealistic limits, such as taking the network size to infinity or assuming a continuum. These asymptotic and analytic approaches can significantly diverge from real or simulated networks when applied at the finite scales of real-world applications. This book offers an approach to overcoming these limitations by introducing operator graph theory, an exact, non-asymptotic set of tools combining graph theory with operator calculus. The book is intended for mathematicians, physicists, and other scientists interested in discrete finite systems and their graph-theoretical description, and in delineating the abstract algebraic structures that characterise such systems. All the necessary background on graph theory and operator calculus is included for readers to understand the potential applications of operator graph theory."

--- I am _a priori_ dubious about the value of this approach, but...]]></description>
<dc:subject>to:NB graph_theory mathematics books:noted downloaded</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:4b9ebeb4b38e/</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_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:books:noted"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:downloaded"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2202.01563">
    <title>[2202.01563] On the Number of Graphs with a Given Histogram</title>
    <dc:date>2022-06-15T18:55:42+00:00</dc:date>
    <link>https://arxiv.org/abs/2202.01563</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Let G be a large (simple, unlabeled) dense graph on n vertices. Suppose that we only know, or can estimate, the empirical distribution of the number of subgraphs F that each vertex in G participates in, for some fixed small graph F. How many other graphs would look essentially the same to us, i.e., would have a similar local structure? In this paper, we derive upper and lower bounds on the number of graphs whose empirical distribution lies close (in the Kolmogorov-Smirnov distance) to that of G. Our bounds are given as solutions to a maximum entropy problem on random graphs of a fixed size k that does not depend on n, under d global density constraints. The bounds are asymptotically close, with a gap that vanishes with d at a rate that depends on the concentration function of the center of the Kolmogorov-Smirnov ball."]]></description>
<dc:subject>to:NB graph_theory graph_limits probability combinatorics</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:976d4ca4d910/</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_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_limits"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:probability"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:combinatorics"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2203.07230">
    <title>[2203.07230] Laplacian Renormalization Group for heterogeneous networks</title>
    <dc:date>2022-06-06T12:56:59+00:00</dc:date>
    <link>https://arxiv.org/abs/2203.07230</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["The renormalization group is the cornerstone of the modern theory of universality and phase transitions, a powerful tool to scrutinize symmetries and organizational scales in dynamical systems. However, its network counterpart is particularly challenging due to correlations between intertwined scales. To date, the explorations are based on hidden geometries hypotheses. Here, we propose a Laplacian RG diffusion-based picture in complex networks, defining both the Kadanoff supernodes' concept, the momentum space procedure, \emph{á la Wilson}, and applying this RG scheme to real networks in a natural and parsimonious way."]]></description>
<dc:subject>to:NB renormalization graph_theory network_data_analysis</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:9aea199820a2/</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:renormalization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2201.04888">
    <title>[2201.04888] Generating graphs randomly</title>
    <dc:date>2022-03-13T18:10:00+00:00</dc:date>
    <link>https://arxiv.org/abs/2201.04888</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Graphs are used in many disciplines to model the relationships that exist between objects in a complex discrete system. Researchers may wish to compare a network of interest to a "typical" graph from a family (or ensemble) of graphs which are similar in some way. One way to do this is to take a sample of several random graphs from the family, to gather information about what is "typical". Hence there is a need for algorithms which can generate graphs uniformly (or approximately uniformly) at random from the given family. Since a large sample may be required, the algorithm should also be computationally efficient.
"Rigorous analysis of such algorithms is often challenging, involving both combinatorial and probabilistic arguments. We will focus mainly on the set of all simple graphs with a particular degree sequence, and describe several different algorithms for sampling graphs from this family uniformly, or almost uniformly."
]]></description>
<dc:subject>in_NB graph_sampling graph_theory via:vaguery</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:a26a182d85d7/</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:graph_sampling"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:via:vaguery"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2103.04668">
    <title>[2103.04668] The distance backbone of complex networks</title>
    <dc:date>2021-05-14T01:54:54+00:00</dc:date>
    <link>https://arxiv.org/abs/2103.04668</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Redundancy needs more precise characterization as it is a major factor in the evolution and robustness of networks of multivariate interactions. We investigate the complexity of such interactions by inferring a connection transitivity that includes all possible measures of path length for weighted graphs. The result, without breaking the graph into smaller components, is a distance backbone subgraph sufficient to compute all shortest paths. This is important for understanding the dynamics of spread and communication phenomena in real-world networks. The general methodology we formally derive yields a principled graph reduction technique and provides a finer characterization of the triangular geometry of all edges -- those that contribute to shortest paths and those that do not but are involved in other network phenomena. We demonstrate that the distance backbone is very small in large networks across domains ranging from air traffic to the human brain connectome, revealing that network robustness to attacks and failures seems to stem from surprisingly vast amounts of redundancy."]]></description>
<dc:subject>to:NB network_data_analysis robustness graph_theory rocha.luis_m.</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:112f46a8d854/</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:robustness"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:rocha.luis_m."/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2105.03122">
    <title>[2105.03122] From Graph Centrality to Data Depth</title>
    <dc:date>2021-05-10T22:51:17+00:00</dc:date>
    <link>https://arxiv.org/abs/2105.03122</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Given a sample of points in a Euclidean space, we can define a notion of depth by forming a neighborhood graph and applying a notion of centrality. In the present paper, we focus on the degree, iterates of the H-index, and the coreness, which are all well-known measures of centrality. We study their behaviors when applied to a sample of points drawn i.i.d. from an underlying density and with a connectivity radius properly chosen. Equivalently, we study these notions of centrality in the context of random neighborhood graphs. We show that, in the large-sample limit and under some standard condition on the connectivity radius, the degree converges to the likelihood depth (unsurprisingly), while iterates of the H-index and the coreness converge to new notions of depth."]]></description>
<dc:subject>to:NB graph_theory data_analysis statistics</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:ed8fb8095e49/</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_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://www.annualreviews.org/doi/abs/10.1146/annurev-control-061820-083817">
    <title>Model Reduction Methods for Complex Network Systems | Annual Review of Control, Robotics, and Autonomous Systems</title>
    <dc:date>2021-05-06T13:48:38+00:00</dc:date>
    <link>https://www.annualreviews.org/doi/abs/10.1146/annurev-control-061820-083817</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Network systems consist of subsystems and their interconnections and provide a powerful framework for the analysis, modeling, and control of complex systems. However, subsystems may have high-dimensional dynamics and a large number of complex interconnections, and it is therefore relevant to study reduction methods for network systems. Here, we provide an overview of reduction methods for both the topological (interconnection) structure of a network and the dynamics of the nodes while preserving structural properties of the network. We first review topological complexity reduction methods based on graph clustering and aggregation, producing a reduced-order network model. Next, we consider reduction of the nodal dynamics using extensions of classical methods while preserving the stability and synchronization properties. Finally, we present a structure-preserving generalized balancing method for simultaneously simplifying the topological structure and the order of the nodal dynamics."]]></description>
<dc:subject>to:NB dynamical_systems networks dimension_reduction graph_theory</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:b03640a0c4ff/</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:dynamical_systems"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:networks"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:dimension_reduction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_theory"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://www.annualreviews.org/doi/abs/10.1146/annurev-control-061520-010504">
    <title>Factor Graphs: Exploiting Structure in Robotics | Annual Review of Control, Robotics, and Autonomous Systems</title>
    <dc:date>2021-05-06T13:47:56+00:00</dc:date>
    <link>https://www.annualreviews.org/doi/abs/10.1146/annurev-control-061520-010504</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Many estimation, planning, and optimal control problems in robotics have an optimization problem at their core. In most of these optimization problems, the objective to be maximized or minimized is composed of many different factors or terms that are local in nature—that is, they depend only on a small subset of the variables. A particularly insightful way of modeling this locality structure is to use the concept of factor graphs, a bipartite graphical model in which factors represent functions on subsets of variables. Factor graphs can represent a wide variety of problems across robotics, expose opportunities to improve computational performance, and are beneficial in designing and thinking about how to model a problem, even aside from performance considerations. I discuss each of these three aspects in detail and review several state-of-the-art robotics applications in which factor graphs have been used with great success."]]></description>
<dc:subject>to:NB optimization graph_theory</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:1ceac07582ac/</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:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_theory"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1411.0650">
    <title>[1411.0650] Proof of the satisfiability conjecture for large k</title>
    <dc:date>2021-04-16T19:40:35+00:00</dc:date>
    <link>https://arxiv.org/abs/1411.0650</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We establish the satisfiability threshold for random k-SAT for all k≥k0, with k0 an absolute constant. That is, there exists a limiting density α∗(k) such that a random k-SAT formula of clause density α is with high probability satisfiable for α<α∗, and unsatisfiable for α>α∗. We show that the threshold α∗(k) is given explicitly by the one-step replica symmetry breaking prediction from statistical physics. The proof develops a new analytic method for moment calculations on random graphs, mapping a high-dimensional optimization problem to a more tractable problem of analyzing tree recursions. We believe that our method may apply to a range of random CSPs in the 1-RSB universality class."]]></description>
<dc:subject>to:NB graph_theory computational_statistics theoretical_computer_science sly.allan probability</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:ed405ee4aa25/</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_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:computational_statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:theoretical_computer_science"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:sly.allan"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:probability"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2103.11818">
    <title>[2103.11818] Higher-order Homophily is Combinatorially Impossible</title>
    <dc:date>2021-03-26T20:04:15+00:00</dc:date>
    <link>https://arxiv.org/abs/2103.11818</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Homophily is the seemingly ubiquitous tendency for people to connect with similar others, which is fundamental to how society organizes. Even though many social interactions occur in groups, homophily has traditionally been measured from collections of pairwise interactions involving just two individuals. Here, we develop a framework using hypergraphs to quantify homophily from multiway, group interactions. This framework reveals that many homophilous group preferences are impossible; for instance, men and women cannot simultaneously exhibit preferences for groups where their gender is the majority. This is not a human behavior but rather a combinatorial impossibility of hypergraphs. At the same time, our framework reveals relaxed notions of group homophily that appear in numerous contexts. For example, in order for US members of congress to exhibit high preferences for co-sponsoring bills with their own political party, there must also exist a substantial number of individuals from each party that are willing to co-sponsor bills even when their party is in the minority. Our framework also reveals how gender distribution in group pictures varies with group size, a fact that is overlooked when applying graph-based measures."

--- I would quibble with the phrasing of the abstract; these seem like perfectly coherent _preferences_, which just can't be _satisfied_ (for everyone at once, or at all).  Even at the dyadic level, "homophily" is ambiguous between a preference and an outcome...]]></description>
<dc:subject>to:NB graph_theory combinatorics social_networks homophily kleinberg.jon</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:7111587a8a4c/</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_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:combinatorics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:social_networks"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:homophily"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:kleinberg.jon"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2102.02653">
    <title>[2102.02653] Typicality and entropy of processes on infinite trees</title>
    <dc:date>2021-02-05T20:10:31+00:00</dc:date>
    <link>https://arxiv.org/abs/2102.02653</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Consider a uniformly sampled random d-regular graph on n vertices. If d is fixed and n goes to ∞ then we can relate typical (large probability) properties of such random graph to a family of invariant random processes (called "typical" processes) on the infinite d-regular tree Td. This correspondence between ergodic theory on Td and random regular graphs is already proven to be fruitful in both directions. This paper continues the investigation of typical processes with a special emphasis on entropy. We study a natural notion of micro-state entropy for invariant processes on Td. It serves as a quantitative refinement of the notion of typicality and is tightly connected to the asymptotic free energy in statistical physics. Using entropy inequalities, we provide new sufficient conditions for typicality for edge Markov processes. We also extend these notions and results to processes on unimodular Galton-Watson random trees."]]></description>
<dc:subject>to:NB stochastic_processes graph_theory information_theory</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:88b975c9c1fd/</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_processes"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:information_theory"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://journals.aps.org/pre/abstract/10.1103/PhysRevE.103.012309">
    <title>Phys. Rev. E 103, 012309 (2021) - Random graphs with arbitrary clustering and their applications</title>
    <dc:date>2021-01-27T15:10:56+00:00</dc:date>
    <link>https://journals.aps.org/pre/abstract/10.1103/PhysRevE.103.012309</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["The structure of many real networks is not locally treelike and, hence, network analysis fails to characterize their bond percolation properties. In a recent paper [P. Mann, V. A. Smith, J. B. O. Mitchell, and S. Dobson, arXiv:2006.06744], we developed analytical solutions to the percolation properties of random networks with homogeneous clustering (clusters whose nodes are degree equivalent). In this paper, we extend this model to investigate networks that contain clusters whose nodes are not degree equivalent, including multilayer networks. Through numerical examples, we show how this method can be used to investigate the properties of random complex networks with arbitrary clustering, extending the applicability of the configuration model and generating function formulation."]]></description>
<dc:subject>to:NB network_data_analysis graph_theory to_read to_teach:baby-nets</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:08c135eafbad/</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:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_teach:baby-nets"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://nowpublishers.com/article/Details/MAL-078-2">
    <title>now publishers - Data Analytics on Graphs Part II: Signals on Graphs</title>
    <dc:date>2021-01-14T19:21:27+00:00</dc:date>
    <link>https://nowpublishers.com/article/Details/MAL-078-2</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["The area of Data Analytics on graphs deals with information processing of data acquired on irregular but structured graph domains. The focus of Part I of this monograph has been on both the fundamental and higher-order graph properties, graph topologies, and spectral representations of graphs. Part I also establishes rigorous frameworks for vertex clustering and graph segmentation, and illustrates the power of graphs in various data association tasks. Part II embarks on these concepts to address the algorithmic and practical issues related to data/signal processing on graphs, with the focus on the analysis and estimation of both deterministic and random data on graphs. The fundamental ideas related to graph signals are introduced through a simple and intuitive, yet general enough case study of multisensor temperature field estimation. The concept of systems on graph is defined using graph signal shift operators, which generalize the corresponding principles from traditional learning systems. At the core of the spectral domain representation of graph signals and systems is the Graph Fourier Transform (GFT), defined based on the eigendecomposition of both the adjacency matrix and the graph Laplacian. Spectral domain representations are then used as the basis to introduce graph signal filtering concepts and address their design, including Chebyshev series polynomial approximation. Ideas related to the sampling of graph signals, and in particular the challenging topic of data dimensionality reduction through graph subsampling, are presented and further linked with compressive sensing. The principles of time-varying signals on graphs and basic definitions related to random graph signals are next reviewed. Localized graph signal analysis in the joint vertex-spectral domain is referred to as the vertex-frequency analysis, since it can be considered as an extension of classical time-frequency analysis to the graph serving as signal domain. Important aspects of the local graph Fourier transform (LGFT) are covered, together with its various forms including the graph spectral and vertex domain windows and the inversion conditions and relations. A link between the LGFT with a varying spectral window and the spectral graph wavelet transform (SGWT) is also established. Realizations of the LGFT and SGWT using polynomial (Chebyshev) approximations of the spectral functions are further considered and supported by examples. Finally, energy versions of the vertex-frequency representations are introduced, along with their relations with classical timefrequency analysis, including a vertex-frequency distribution that can satisfy the marginal properties. The material is supported by illustrative examples."

]]></description>
<dc:subject>to:NB data_mining graph_theory network_data_analysis fourier_analysis</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:2f8de14b2961/</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:graph_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:fourier_analysis"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://nowpublishers.com/article/Details/MAL-078-1">
    <title>now publishers - Data Analytics on Graphs Part I: Graphs and Spectra on Graphs</title>
    <dc:date>2021-01-14T19:20:33+00:00</dc:date>
    <link>https://nowpublishers.com/article/Details/MAL-078-1</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["The area of Data Analytics on graphs promises a paradigm shift, as we approach information processing of new classes of data which are typically acquired on irregular but structured domains (such as social networks, various ad-hoc sensor networks). Yet, despite the long history of Graph Theory, current approaches tend to focus on aspects of optimisation of graphs themselves rather than on eliciting strategies relevant to the objective application of the graph paradigm, such as detection, estimation, statistical and probabilistic inference, clustering and separation from signals and data acquired on graphs. In order to bridge this gap, we first revisit graph topologies from a Data Analytics point of view, to establish a taxonomy of graph networks through a linear algebraic formalism of graph topology (vertices, connections, directivity). This serves as a basis for spectral analysis of graphs, whereby the eigenvalues and eigenvectors of graph Laplacian and adjacency matrices are shown to convey physical meaning related to both graph topology and higher-order graph properties, such as cuts, walks, paths, and neighborhoods. Through a number of carefully chosen examples, we demonstrate that the isomorphic nature of graphs enables both the basic properties of data observed on graphs and their descriptors (features) to be preserved throughout the data analytics process, even in the case of reordering of graph vertices, where classical approaches fail. Next, to illustrate the richness and flexibility of estimation strategies performed on graph signals, spectral analysis of graphs is introduced through eigenanalysis of mathematical descriptors of graphs and in a generic way. Finally, benefiting from enhanced degrees of freedom associated with graph representations, a framework for vertex clustering and graph segmentation is established based on graph spectral representation (eigenanalysis) which demonstrates the power of graphs in various data association tasks, from image clustering and segmentation trough to low-dimensional manifold representation. The supporting examples demonstrate the promise of Graph Data Analytics in modeling structural and functional/semantic inferences. At the same time, Part I serves as a basis for Part II and Part III which deal with theory, methods and applications of processing Data on Graphs and Graph Topology Learning from data."]]></description>
<dc:subject>to:NB graph_theory data_mining network_data_analysis spectral_methods</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:bfd5d06856f6/</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_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:data_mining"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:spectral_methods"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2101.03618">
    <title>[2101.03618] Network clique cover approximation to analyze complex contagions through group interactions</title>
    <dc:date>2021-01-12T21:03:22+00:00</dc:date>
    <link>https://arxiv.org/abs/2101.03618</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Contagion processes have been proven to fundamentally depend on the structural properties of the interaction networks conveying them. Many real networked systems -- especially social ones -- are characterized by clustered substructures representing either collections of all-to-all pair-wise interactions (cliques) and/or group interactions, involving many of their members at once. In this work we focus on interaction structures represented as simplicial complexes, in which a group interaction is identified with a face. We present a microscopic discrete-time model of complex contagion for which a susceptible-infected-susceptible dynamics is considered. Introducing a particular edge clique cover and a heuristic to find it, the model accounts for the high-order state correlations among the members of the substructures (cliques/simplices). The mathematical tractability of the model allows for the analytical computation of the epidemic threshold, thus extending to structured populations some primary features of the critical properties of mean-field models. Overall, the model is found in remarkable agreement with numerical simulations."]]></description>
<dc:subject>to:NB graph_theory epidemics_on_networks</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:a0384cca2b54/</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_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:epidemics_on_networks"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2012.12309">
    <title>[2012.12309] Influence Maximization Under Generic Threshold-based Non-submodular Model</title>
    <dc:date>2020-12-26T17:40:14+00:00</dc:date>
    <link>https://arxiv.org/abs/2012.12309</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["As a widely observable social effect, influence diffusion refers to a process where innovations, trends, awareness, etc. spread across the network via the social impact among individuals. Motivated by such social effect, the concept of influence maximization is coined, where the goal is to select a bounded number of the most influential nodes (seed nodes) from a social network so that they can jointly trigger the maximal influence diffusion. A rich body of research in this area is performed under statistical diffusion models with provable submodularity, which essentially simplifies the problem as the optimal result can be approximated by the simple greedy search. When the diffusion models are non-submodular, however, the research community mostly focuses on how to bound/approximate them by tractable submodular functions so as to estimate the optimal result. In other words, there is still a lack of efficient methods that can directly resolve non-submodular influence maximization problems. In this regard, we fill the gap by proposing seed selection strategies using network graphical properties in a generalized threshold-based model, called influence barricade model, which is non-submodular. Specifically, under this model, we first establish theories to reveal graphical conditions that ensure the network generated by node removals has the same optimal seed set as that in the original network. We then exploit these theoretical conditions to develop efficient algorithms by strategically removing less-important nodes and selecting seeds only in the remaining network. To the best of our knowledge, this is the first graph-based approach that directly tackles non-submodular influence maximization."

--- Of course, social influence is not observationally identified, and from what I can tell this whole literature just ignores issues of homophily (even homophily on measured covariates...), but this looks interesting within that mathematical game.]]></description>
<dc:subject>to:NB social_networks social_influence optimization graph_theory re:do-institutions-evolve</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:aafc35a577e2/</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:social_networks"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:social_influence"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:do-institutions-evolve"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1705.06815">
    <title>[1705.06815] Large deviations for subcritical bootstrap percolation on the random graph</title>
    <dc:date>2020-12-16T17:39:38+00:00</dc:date>
    <link>https://arxiv.org/abs/1705.06815</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We study atypical behavior in bootstrap percolation on the Erdős-Rényi random graph. Initially a set S is infected. Other vertices are infected once at least r of their neighbors become infected. Janson et al. (2012) locates the critical size of S, above which it is likely that the infection will spread almost everywhere. Below this threshold, a central limit theorem is proved for the size of the eventually infected set. In this note, we calculate the rate function for the event that a small set S eventually infects an unexpected number of vertices, and identify the least-cost trajectory realizing such a large deviation."]]></description>
<dc:subject>to:NB epidemics_on_networks stochastic_processes graph_theory large_deviations re:do-institutions-evolve</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:e969f493b9fa/</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:epidemics_on_networks"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:stochastic_processes"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:large_deviations"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:do-institutions-evolve"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1906.08806">
    <title>[1906.08806] The Moran forest</title>
    <dc:date>2020-12-16T17:37:58+00:00</dc:date>
    <link>https://arxiv.org/abs/1906.08806</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Starting from any graph on {1,…,n}, consider the Markov chain where at each time-step a uniformly chosen vertex is disconnected from all of its neighbors and reconnected to another uniformly chosen vertex. This Markov chain has a stationary distribution whose support is the set of non-empty forests on {1,…,n}. The random forest corresponding to this stationary distribution has interesting connections with the uniform rooted labeled tree and the uniform attachment tree. We fully characterize its degree distribution, the distribution of its number of trees, and the limit distribution of the size of a tree sampled uniformly. We also show that the size of the largest tree is asymptotically αlogn, where α=(1−log(e−1))−1≈2.18, and that the degree of the most connected vertex is asymptotically logn/loglogn."]]></description>
<dc:subject>to:NB graph_theory stochastic_processes</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:cab6bb488bfe/</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_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:stochastic_processes"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2012.05129">
    <title>[2012.05129] Approximate Network Symmetry</title>
    <dc:date>2020-12-10T04:08:14+00:00</dc:date>
    <link>https://arxiv.org/abs/2012.05129</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We define a new measure of network symmetry that is capable of capturing approximate global symmetries of networks. We apply this measure to different networks sampled from several classic network models, as well as several real-world networks. We find that among the network models that we have examined, Erdös-Rényi networks have the least levels of symmetry, and Random Geometric Graphs are likely to have high levels of symmetry. We find that our network symmetry measure can capture properties of network structure, and help us gain insights on the structure of real-world networks. Moreover, our network symmetry measure is capable of capturing imperfect network symmetry, which would have been undetected if only perfect symmetry is considered."]]></description>
<dc:subject>to:NB graph_theory network_data_analysis</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:2972e4b50a6b/</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_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1910.09483">
    <title>[1910.09483] Sampling random graph homomorphisms and applications to network data analysis</title>
    <dc:date>2019-10-22T13:21:40+00:00</dc:date>
    <link>https://arxiv.org/abs/1910.09483</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["A graph homomorphism is a map between two graphs that preserves adjacency relations. We consider the problem of sampling a random graph homomorphism from a graph F into a large network . When  is the complete graph with q nodes, this becomes the well-known problem of sampling uniform q-colorings of F. We propose two complementary MCMC algorithms for sampling a random graph homomorphisms and establish bounds on their mixing times and concentration of their time averages. Based on our sampling algorithms, we propose a novel framework for network data analysis that circumvents some of the drawbacks in methods based on independent and neigborhood sampling. Various time averages of the MCMC trajectory give us real-, function-, and network-valued computable observables, including well-known ones such as homomorphism density and average clustering coefficient. One of the main observable we propose is called the conditional homomorphism density profile, which reveals hierarchical structure of the network. Furthermore, we show that these network observables are stable with respect to a suitably renormalized cut distance between networks. We also provide various examples and simulations demonstrating our framework through synthetic and real-world networks. For instance, we apply our framework to analyze Word Adjacency Networks of a 45 novels data set and propose an authorship attribution scheme using motif sampling and conditional homomorphism density profiles."]]></description>
<dc:subject>to:NB network_data_analysis network_sampling graph_theory computational_statistics statistics</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:4d49558be133/</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:network_sampling"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:computational_statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1908.08572">
    <title>[1908.08572] From Community to Role-based Graph Embeddings</title>
    <dc:date>2019-08-27T15:43:41+00:00</dc:date>
    <link>https://arxiv.org/abs/1908.08572</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Roles are sets of structurally similar nodes that are more similar to nodes inside the set than outside, whereas communities are sets of nodes with more connections inside the set than outside (based on proximity/closeness, density). Roles and communities are fundamentally different but important complementary notions. Recently, the notion of roles has become increasingly important and has gained a lot of attention due to the proliferation of work on learning representations (node/edge embeddings) from graphs that preserve the notion of roles. Unfortunately, recent work has sometimes confused the notion of roles and communities leading to misleading or incorrect claims about the capabilities of network embedding methods. As such, this manuscript seeks to clarify the differences between roles and communities, and formalize the general mechanisms (e.g., random walks, feature diffusion) that give rise to community or role-based embeddings. We show mathematically why embedding methods based on these identified mechanisms are either community or role-based. These mechanisms are typically easy to identify and can help researchers quickly determine whether a method is more prone to learn community or role-based embeddings. Furthermore, they also serve as a basis for developing new and better methods for community or role-based embeddings. Finally, we analyze and discuss the applications and data characteristics where community or role-based embeddings are most appropriate."]]></description>
<dc:subject>to:NB graph_theory community_discovery network_data_analysis</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:f83ae343f882/</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_theory"/>
	<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:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1902.03002">
    <title>[1902.03002] Covariance and Correlation Kernels on a Graph in the Generalized Bag-of-Paths Formalism</title>
    <dc:date>2019-08-20T14:26:32+00:00</dc:date>
    <link>https://arxiv.org/abs/1902.03002</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["This work derives closed-form expressions computing the expectation of co-presences and of number of co-occurences of nodes on paths sampled from a network according to general path weights (a bag of paths). The underlying idea is that two nodes are considered as similar when they appear together on (preferably short) paths of the network. The results are obtained for both regular and hitting paths and serve as a basis for computing new covariance and correlation measures between nodes. Experiments on semi-supervised classification show that the introduced similarity measures provide competitive performances compared to other state-of-the-art distances and similarities."]]></description>
<dc:subject>to:NB network_data_analysis to_teach:baby-nets probability graph_theory</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:e80f55bccc6c/</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:to_teach:baby-nets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:probability"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_theory"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1908.06057">
    <title>[1908.06057] Generalized group-based epidemic model for spreading processes on networks: GgroupEM</title>
    <dc:date>2019-08-19T13:20:28+00:00</dc:date>
    <link>https://arxiv.org/abs/1908.06057</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We develop a generalized group-based epidemic model (GgroupEM) framework for any compartmental epidemic model (for example; susceptible-infected-susceptible, susceptible-infected-recovered, susceptible-exposed-infected-recovered). Here, a group consists of a collection of individual nodes. This model can be used to understand the important dynamic characteristics of a stochastic epidemic spreading over very large complex networks, being informative about the state of groups. Aggregating nodes by groups, the state space becomes smaller than the individual-based approach at the cost of aggregation error, which is strongly bounded by the isoperimetric inequality. We also develop a mean-field approximation of this framework to further reduce the state-space size. Finally, we extend the GgroupEM to multilayer networks. Since the group-based framework is computationally less expensive and faster than an individual-based framework, then this framework is useful when the simulation time is important."]]></description>
<dc:subject>epidemics_on_networks epidemic_models macro_from_micro graph_theory in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:aeab934e4e4d/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:epidemics_on_networks"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:epidemic_models"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:macro_from_micro"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://www.cambridge.org/core/books/inequalities-for-graph-eigenvalues/0047197D65BB927AAC906784CC7F3774#fndtn-information">
    <title>Inequalities for Graph Eigenvalues by Zoran Stanić</title>
    <dc:date>2019-01-06T01:37:06+00:00</dc:date>
    <link>https://www.cambridge.org/core/books/inequalities-for-graph-eigenvalues/0047197D65BB927AAC906784CC7F3774#fndtn-information</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Written for mathematicians working with the theory of graph spectra, this book explores more than 400 inequalities for eigenvalues of the six matrices associated with finite simple graphs: the adjacency matrix, Laplacian matrix, signless Laplacian matrix, normalized Laplacian matrix, Seidel matrix, and distance matrix. The book begins with a brief survey of the main results and selected applications to related topics, including chemistry, physics, biology, computer science, and control theory. The author then proceeds to detail proofs, discussions, comparisons, examples, and exercises. Each chapter ends with a brief survey of further results. The author also points to open problems and gives ideas for further reading."]]></description>
<dc:subject>to:NB books:noted downloaded spectral_methods graph_theory mathematics</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:b9f193a4e2f6/</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:books:noted"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:downloaded"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:spectral_methods"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:mathematics"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1705.02801">
    <title>[1705.02801] Graph Embedding Techniques, Applications, and Performance: A Survey</title>
    <dc:date>2018-08-14T15:55:59+00:00</dc:date>
    <link>https://arxiv.org/abs/1705.02801</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Graphs, such as social networks, word co-occurrence networks, and communication networks, occur naturally in various real-world applications. Analyzing them yields insight into the structure of society, language, and different patterns of communication. Many approaches have been proposed to perform the analysis. Recently, methods which use the representation of graph nodes in vector space have gained traction from the research community. In this survey, we provide a comprehensive and structured analysis of various graph embedding techniques proposed in the literature. We first introduce the embedding task and its challenges such as scalability, choice of dimensionality, and features to be preserved, and their possible solutions. We then present three categories of approaches based on factorization methods, random walks, and deep learning, with examples of representative algorithms in each category and analysis of their performance on various tasks. We evaluate these state-of-the-art methods on a few common datasets and compare their performance against one another. Our analysis concludes by suggesting some potential applications and future directions. We finally present the open-source Python library we developed, named GEM (Graph Embedding Methods, available at this https URL), which provides all presented algorithms within a unified interface to foster and facilitate research on the topic."]]></description>
<dc:subject>graph_theory network_data_analysis visual_display_of_quantitative_information geometry re:hyperbolic_networks via:rvenkat in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:9c85a77742f4/</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:network_data_analysis"/>
	<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:geometry"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:hyperbolic_networks"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:via:rvenkat"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://mitpress.mit.edu/books/mathematics-big-data">
    <title>Mathematics of Big Data | The MIT Press</title>
    <dc:date>2018-07-13T13:03:19+00:00</dc:date>
    <link>https://mitpress.mit.edu/books/mathematics-big-data</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Today, the volume, velocity, and variety of data are increasing rapidly across a range of fields, including Internet search, healthcare, finance, social media, wireless devices, and cybersecurity. Indeed, these data are growing at a rate beyond our capacity to analyze them. The tools—including spreadsheets, databases, matrices, and graphs—developed to address this challenge all reflect the need to store and operate on data as whole sets rather than as individual elements. This book presents the common mathematical foundations of these data sets that apply across many applications and technologies. Associative arrays unify and simplify data, allowing readers to look past the differences among the various tools and leverage their mathematical similarities in order to solve the hardest big data challenges.
"The book first introduces the concept of the associative array in practical terms, presents the associative array manipulation system D4M (Dynamic Distributed Dimensional Data Model), and describes the application of associative arrays to graph analysis and machine learning. It provides a mathematically rigorous definition of associative arrays and describes the properties of associative arrays that arise from this definition. Finally, the book shows how concepts of linearity can be extended to encompass associative arrays. Mathematics of Big Data can be used as a textbook or reference by engineers, scientists, mathematicians, computer scientists, and software engineers who analyze big data."]]></description>
<dc:subject>to:NB books:noted mathematics computation graph_theory color_me_skeptical</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:c0c3270cc170/</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:books:noted"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:computation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:color_me_skeptical"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.cambridge.org/us/academic/subjects/mathematics/discrete-mathematics-information-theory-and-coding/eigenvalues-multiplicities-and-graphs?format=HB&amp;WT.mc_id=Cambridge%2BTracts%2Bin%2BMathematics%2BCluster#OFbA1DJep21QxzhX.97">
    <title>Eigenvalues multiplicities and graphs | Discrete mathematics, information theory and coding | Cambridge University Press</title>
    <dc:date>2018-02-02T16:51:33+00:00</dc:date>
    <link>http://www.cambridge.org/us/academic/subjects/mathematics/discrete-mathematics-information-theory-and-coding/eigenvalues-multiplicities-and-graphs?format=HB&amp;WT.mc_id=Cambridge%2BTracts%2Bin%2BMathematics%2BCluster#OFbA1DJep21QxzhX.97</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["The arrangement of nonzero entries of a matrix, described by the graph of the matrix, limits the possible geometric multiplicities of the eigenvalues, which are far more limited by this information than algebraic multiplicities or the numerical values of the eigenvalues. This book gives a unified development of how the graph of a symmetric matrix influences the possible multiplicities of its eigenvalues. While the theory is richest in cases where the graph is a tree, work on eigenvalues, multiplicities and graphs has provided the opportunity to identify which ideas have analogs for non-trees, and those for which trees are essential. It gathers and organizes the fundamental ideas to allow students and researchers to easily access and investigate the many interesting questions in the subject."]]></description>
<dc:subject>to:NB books:noted graph_theory mathematics markov_models</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:f0123af7ce4f/</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:books:noted"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:markov_models"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1311.6425">
    <title>[1311.6425] Robust Multimodal Graph Matching: Sparse Coding Meets Graph Matching</title>
    <dc:date>2016-12-01T20:28:23+00:00</dc:date>
    <link>https://arxiv.org/abs/1311.6425</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Graph matching is a challenging problem with very important applications in a wide range of fields, from image and video analysis to biological and biomedical problems. We propose a robust graph matching algorithm inspired in sparsity-related techniques. We cast the problem, resembling group or collaborative sparsity formulations, as a non-smooth convex optimization problem that can be efficiently solved using augmented Lagrangian techniques. The method can deal with weighted or unweighted graphs, as well as multimodal data, where different graphs represent different types of data. The proposed approach is also naturally integrated with collaborative graph inference techniques, solving general network inference problems where the observed variables, possibly coming from different modalities, are not in correspondence. The algorithm is tested and compared with state-of-the-art graph matching techniques in both synthetic and real graphs. We also present results on multimodal graphs and applications to collaborative inference of brain connectivity from alignment-free functional magnetic resonance imaging (fMRI) data. The code is publicly available."]]></description>
<dc:subject>to:NB to_read network_comparison graph_theory network_data_analysis statistics information_theory re:network_differences</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:596102d3a2b4/</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:network_comparison"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_theory"/>
	<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:information_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:network_differences"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://cs.brown.edu/~rt/gdhandbook/">
    <title>Handbook of Graph Drawing and Visualization</title>
    <dc:date>2016-05-07T18:12:38+00:00</dc:date>
    <link>https://cs.brown.edu/~rt/gdhandbook/</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA[Roberto Tamassia, Editor
CRC Press
June 24, 2013]]></description>
<dc:subject>in_NB books:noted graph_theory network_visualization to_teach:baby-nets</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:e8a6cd8b5896/</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:books:noted"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_visualization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_teach:baby-nets"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.cambridge.org/us/academic/subjects/mathematics/discrete-mathematics-information-theory-and-coding/random-graphs-geometry-and-asymptotic-structure?format=HB&amp;isbn=9781107136571">
    <title>Random Graphs, Geometry and Asymptotic Structure | Cambridge University Press</title>
    <dc:date>2016-03-28T03:02:33+00:00</dc:date>
    <link>http://www.cambridge.org/us/academic/subjects/mathematics/discrete-mathematics-information-theory-and-coding/random-graphs-geometry-and-asymptotic-structure?format=HB&amp;isbn=9781107136571</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["The theory of random graphs is a vital part of the education of any researcher entering the fascinating world of combinatorics. However, due to their diverse nature, the geometric and structural aspects of the theory often remain an obscure part of the formative study of young combinatorialists and probabilists. Moreover, the theory itself, even in its most basic forms, is often considered too advanced to be part of undergraduate curricula, and those who are interested usually learn it mostly through self-study, covering a lot of its fundamentals but little of the more recent developments. This book provides a self-contained and concise introduction to recent developments and techniques for classical problems in the theory of random graphs. Moreover, it covers geometric and topological aspects of the theory and introduces the reader to the diversity and depth of the methods that have been devised in this context."]]></description>
<dc:subject>to:NB books:noted graph_theory stochastic_processes mathematics</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:df0329333b9b/</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:books:noted"/>
	<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:mathematics"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://link.springer.com/article/10.1007/BF01200757">
    <title>The geometry of graphs and some of its algorithmic applications (Linial, London and Rabinovich, 1995)</title>
    <dc:date>2015-07-14T04:02:31+00:00</dc:date>
    <link>http://link.springer.com/article/10.1007/BF01200757</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["In this paper we explore some implications of viewing graphs asgeometric objects. This approach offers a new perspective on a number of graph-theoretic and algorithmic problems. There are several ways to model graphs geometrically and our main concern here is with geometric representations that respect themetric of the (possibly weighted) graph. Given a graphG we map its vertices to a normed space in an attempt to (i) keep down the dimension of the host space, and (ii) guarantee a smalldistortion, i.e., make sure that distances between vertices inG closely match the distances between their geometric images.
"In this paper we develop efficient algorithms for embedding graphs low-dimensionally with a small distortion. Further algorithmic applications include:
"•A simple, unified approach to a number of problems on multicommodity flows, including the Leighton-Rao Theorem [37] and some of its extensions. We solve an open question in this area, showing that the max-flow vs. min-cut gap in thek-commodities problem isO(logk). Our new deterministic polynomial-time algorithm finds a (nearly tight) cut meeting this bound.
"•For graphs embeddable in low-dimensional spaces with a small distortion, we can find low-diameter decompositions (in the sense of [7] and [43]). The parameters of the decomposition depend only on the dimension and the distortion and not on the size of the graph.
"•In graphs embedded this way, small balancedseparators can be found efficiently.
"Given faithful low-dimensional representations of statistical data, it is possible to obtain meaningful and efficientclustering. This is one of the most basic tasks in pattern-recognition. For the (mostly heuristic) methods used in the practice of pattern-recognition, see [20], especially chapter 6.
"Our studies of multicommodity flows also imply that every embedding of (the metric of) ann-vertex, constant-degree expander into a Euclidean space (of any dimension) has distortion Ω(logn). This result is tight, and closes a gap left open by Bourgain [12]."

--- So why don't we think of communities in terms of low-diameter decompositions?]]></description>
<dc:subject>in_NB graph_theory dimension_reduction mathematics random_projections clustering have_read</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:bfbac4c36470/</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:graph_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:dimension_reduction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:random_projections"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<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.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.pnas.org/content/112/10/2942.abstract.html">
    <title>On convex relaxation of graph isomorphism</title>
    <dc:date>2015-03-12T01:10:15+00:00</dc:date>
    <link>http://www.pnas.org/content/112/10/2942.abstract.html</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We consider the problem of exact and inexact matching of weighted undirected graphs, in which a bijective correspondence is sought to minimize a quadratic weight disagreement. This computationally challenging problem is often relaxed as a convex quadratic program, in which the space of permutations is replaced by the space of doubly stochastic matrices. However, the applicability of such a relaxation is poorly understood. We define a broad class of friendly graphs characterized by an easily verifiable spectral property. We prove that for friendly graphs, the convex relaxation is guaranteed to find the exact isomorphism or certify its inexistence. This result is further extended to approximately isomorphic graphs, for which we develop an explicit bound on the amount of weight disagreement under which the relaxation is guaranteed to find the globally optimal approximate isomorphism. We also show that in many cases, the graph matching problem can be further harmlessly relaxed to a convex quadratic program with only n separable linear equality constraints, which is substantially more efficient than the standard relaxation involving 2n equality and n2 inequality constraints. Finally, we show that our results are still valid for unfriendly graphs if additional information in the form of seeds or attributes is allowed, with the latter satisfying an easy to verify spectral characteristic."]]></description>
<dc:subject>graph_theory computational_complexity optimization convexity network_data_analysis re:network_differences in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:ba1653300c14/</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:computational_complexity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:convexity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<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://press.princeton.edu/titles/10314.html">
    <title>Benjamin, A. and Chartrand, G., Zhang, P.: The Fascinating World of Graph Theory (eBook and Hardcover).</title>
    <dc:date>2015-02-06T00:35:16+00:00</dc:date>
    <link>http://press.princeton.edu/titles/10314.html</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["The fascinating world of graph theory goes back several centuries and revolves around the study of graphs—mathematical structures showing relations between objects. With applications in biology, computer science, transportation science, and other areas, graph theory encompasses some of the most beautiful formulas in mathematics—and some of its most famous problems. For example, what is the shortest route for a traveling salesman seeking to visit a number of cities in one trip? What is the least number of colors needed to fill in any map so that neighboring regions are always colored differently? Requiring readers to have a math background only up to high school algebra, this book explores the questions and puzzles that have been studied, and often solved, through graph theory. In doing so, the book looks at graph theory’s development and the vibrant individuals responsible for the field’s growth.
"Introducing graph theory’s fundamental concepts, the authors explore a diverse plethora of classic problems such as the Lights Out Puzzle, the Minimum Spanning Tree Problem, the Königsberg Bridge Problem, the Chinese Postman Problem, a Knight’s Tour, and the Road Coloring Problem. They present every type of graph imaginable, such as bipartite graphs, Eulerian graphs, the Petersen graph, and trees. Each chapter contains math exercises and problems for readers to savor."

--- For a freshman seminar?

--- Link: https://www.jstor.org/stable/j.ctt9qh0pv]]></description>
<dc:subject>books:noted mathematics graph_theory in_NB downloaded</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:5f7e6e967b72/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:books:noted"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:downloaded"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1405.3133">
    <title>[1405.3133] Graph Matching: Relax at Your Own Risk</title>
    <dc:date>2015-01-20T04:12:02+00:00</dc:date>
    <link>http://arxiv.org/abs/1405.3133</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Graph matching---aligning a pair of graphs to minimize their edge disagreements---has received wide-spread attention from both theoretical and applied communities over the past several decades, including combinatorics, computer vision, and connectomics. Its attention can be partially attributed to its computational difficulty. Although many heuristics have previously been proposed in the literature to approximately solve graph matching, very few have any theoretical support for their performance. A common technique is to relax the discrete problem to a continuous problem, therefore enabling practitioners to bring gradient-descent-type algorithms to bear. We prove that an indefinite relaxation (when solved exactly) almost always discovers the optimal permutation, while a common convex relaxation almost always fails to discover the optimal permutation. These theoretical results suggest that initializing the indefinite algorithm with the convex optimum might yield improved practical performance. Indeed, experimental results illuminate and corroborate these theoretical findings, demonstrating that excellent results are achieved in both benchmark and real data problems by amalgamating the two approaches."]]></description>
<dc:subject>graph_theory network_data_analysis optimization re:network_differences in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:2937fbd143b8/</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:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:optimization"/>
	<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/1411.1546">
    <title>[1411.1546] Tree decompositions and social graphs</title>
    <dc:date>2015-01-20T04:01:52+00:00</dc:date>
    <link>http://arxiv.org/abs/1411.1546</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Recent work has established that large informatics graphs such as social and information networks have non-trivial tree-like structure when viewed at moderate size scales. Here, we present results from the first detailed empirical evaluation of the use of tree decomposition (TD) heuristics for structure identification and extraction in social graphs. Although TDs have historically been used in structural graph theory and scientific computing, we show that---even with existing TD heuristics developed for those very different areas---TD methods can identify interesting structure in a wide range of realistic informatics graphs. Among other things, we show that TD methods can identify structures that correlate strongly with the core-periphery structure of realistic networks, even when using simple greedy heuristics; we show that the peripheral bags of these TDs correlate well with low-conductance communities (when they exist) found using local spectral computations; and we show that several types of large-scale "ground-truth" communities, defined by demographic metadata on the nodes of the network, are well-localized in the large-scale and/or peripheral structures of the TDs. Our detailed empirical results for different TD heuristics on toy and synthetic networks help to establish a baseline to understand better the behavior of the heuristics on more complex real-world networks; and our results here suggest future directions for the development of improved TD heuristics that are more appropriate for improved structure identification in realistic networks."]]></description>
<dc:subject>network_data_analysis community_discovery statistics graph_theory social_networks in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:36009ab50a6f/</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:graph_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:social_networks"/>
	<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.1007/s11009-012-9311-x">
    <title>Max-Plus Objects to Study the Complexity of Graphs - Springer</title>
    <dc:date>2014-08-06T11:13:21+00:00</dc:date>
    <link>http://link.springer.com/article/10.1007/s11009-012-9311-x</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Given an undirected graph G, we define a new object H G , called the mp-chart of G, in the max-plus algebra. We use it, together with the max-plus permanent, to describe the complexity of graphs. We show how to compute the mean and the variance of H G in terms of the adjacency matrix of G and we give a central limit theorem for H G . Finally, we show that the mp-chart is easily tractable also for the complement graph."]]></description>
<dc:subject>to:NB graph_theory complexity_measures network_data_analysis</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:1ddf520584aa/</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_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:complexity_measures"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1407.0224">
    <title>[1407.0224] Concentric Symmetry</title>
    <dc:date>2014-07-12T01:19:09+00:00</dc:date>
    <link>http://arxiv.org/abs/1407.0224</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["The quantification of symmetries in complex networks is typically done globally in terms of automorphisms. In this work we focus on local symmetries around nodes, which we call connectivity patterns. We develop two topological transformations that allow a concise characterization of the different types of symmetry appearing on networks and apply these concepts to six network models, namely the Erd\H{o}s-R\'enyi, Barab\'asi-Albert, random geometric graph, Waxman, Voronoi and rewired Voronoi models. Real-world networks, namely the scientific areas of Wikipedia, the world-wide airport network and the street networks of Oldenburg and San Joaquin, are also analyzed in terms of the proposed symmetry measurements. Several interesting results, including the high symmetry exhibited by the Erd\H{o}s-R\'enyi model, are observed and discussed."]]></description>
<dc:subject>to:NB graph_theory network_data_analysis</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:9ea97a345981/</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_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1405.1440">
    <title>[1405.1440] Equitable random graphs</title>
    <dc:date>2014-06-07T19:40:03+00:00</dc:date>
    <link>http://arxiv.org/abs/1405.1440</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Random graph models have played a dominant role in the theoretical study of networked systems. The Poisson random graph of Erdos and Renyi, in particular, as well as the so-called configuration model, have served as the starting point for numerous calculations. In this paper we describe another large class of random graph models, which we call equitable random graphs and which are flexible enough to represent networks with diverse degree distributions and many nontrivial types of structure, including community structure, bipartite structure, degree correlations, stratification, and others, yet are exactly solvable for a wide range of properties in the limit of large graph size, including percolation properties, complete spectral density, and the behavior of homogeneous dynamical systems, such as coupled oscillators or epidemic models."]]></description>
<dc:subject>to:NB network_data_analysis graph_theory kith_and_kin newman.mark to_read</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:410175b86f72/</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: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:to_read"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://dl.acm.org/citation.cfm?doid=2435209.2435212">
    <title>Message-Passing Algorithms for Sparse Network Alignment</title>
    <dc:date>2014-04-03T18:43:47+00:00</dc:date>
    <link>http://dl.acm.org/citation.cfm?doid=2435209.2435212</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Network alignment generalizes and unifies several approaches for forming a matching or alignment between the vertices of two graphs. We study a mathematical programming framework for network alignment problem and a sparse variation of it where only a small number of matches between the vertices of the two graphs are possible. We propose a new message passing algorithm that allows us to compute, very efficiently, approximate solutions to the sparse network alignment problems with graph sizes as large as hundreds of thousands of vertices. We also provide extensive simulations comparing our algorithms with two of the best solvers for network alignment problems on two synthetic matching problems, two bioinformatics problems, and three large ontology alignment problems including a multilingual problem with a known labeled alignment."

- Ungated version: https://www.cs.purdue.edu/homes/dgleich/publications/Bayati%202013%20-%20sparse%20belief%20propagation.pdf]]></description>
<dc:subject>to_read network_data_analysis graph_theory network_alignment re:network_differences entableted in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:599da396fcdc/</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:graph_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_alignment"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:network_differences"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:entableted"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1403.3448">
    <title>[1403.3448] Coloring Large Complex Networks</title>
    <dc:date>2014-03-21T17:43:43+00:00</dc:date>
    <link>http://arxiv.org/abs/1403.3448</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Given a large social or information network, how can we partition the vertices into sets (i.e., colors) such that no two vertices linked by an edge are in the same set while minimizing the number of sets used. Despite the obvious practical importance of graph coloring (e.g., network analysis, machine learning, etc), existing work has not systematically investigated or designed methods for large complex networks. In this work, we develop a framework for coloring large complex networks that is (a) accurate with solutions close to optimal, and (b) fast and scalable for large networks with millions of vertices, (c) flexible for use in a variety of applications. Using this framework as a basis, we propose coloring methods designed for the scale and structure of complex networks. In particular, the classes of methods use triangles, triangle-cores, and other egonet properties as a basis. We systematically compare the proposed methods across a wide range of networks and find a significant improvement over traditional approaches in nearly all cases. Additionally, the solutions obtained are nearly optimal and sometimes provably optimal for certain classes of graphs. The experiments indicate the practical significance, accuracy, and scalability of our approach for coloring and analyzing large complex networks."]]></description>
<dc:subject>to:NB network_data_analysis graph_theory</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:c460e4f527da/</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: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/1312.1970">
    <title>[1312.1970] An Algorithmic Theory of Dependent Regularizers, Part 1: Submodular Structure</title>
    <dc:date>2013-12-28T21:24:42+00:00</dc:date>
    <link>http://arxiv.org/abs/1312.1970</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We present an exploration of the rich theoretical connections between several classes of regularized models, network flows, and recent results in submodular function theory. This work unifies key aspects of these problems under a common theory, leading to novel methods for working with several important models of interest in statistics, machine learning and computer vision. 
"In Part 1, we review the concepts of network flows and submodular function optimization theory foundational to our results. We then examine the connections between network flows and the minimum-norm algorithm from submodular optimization, extending and improving several current results. This leads to a concise representation of the structure of a large class of pairwise regularized models important in machine learning, statistics and computer vision. 
In Part 2, we describe the full regularization path of a class of penalized regression problems with dependent variables that includes the graph-guided LASSO and total variation constrained models. This description also motivates a practical algorithm. This allows us to efficiently find the regularization path of the discretized version of TV penalized models. Ultimately, our new algorithms scale up to high-dimensional problems with millions of variables."]]></description>
<dc:subject>to:NB optimization graph_theory lasso</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:3e10f3856769/</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:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:lasso"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1312.5179">
    <title>[1312.5179] The Total Variation on Hypergraphs - Learning on Hypergraphs Revisited</title>
    <dc:date>2013-12-23T22:00:44+00:00</dc:date>
    <link>http://arxiv.org/abs/1312.5179</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Hypergraphs allow one to encode higher-order relationships in data and are thus a very flexible modeling tool. Current learning methods are either based on approximations of the hypergraphs via graphs or on tensor methods which are only applicable under special conditions. In this paper, we present a new learning framework on hypergraphs which fully uses the hypergraph structure. The key element is a family of regularization functionals based on the total variation on hypergraphs."]]></description>
<dc:subject>to:NB smoothing graph_theory hypergraphs optimization</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:0d3670268bfd/</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:smoothing"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:hypergraphs"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:optimization"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1311.7656">
    <title>[1311.7656] Statistical estimation for optimization problems on graphs</title>
    <dc:date>2013-12-16T16:22:22+00:00</dc:date>
    <link>http://arxiv.org/abs/1311.7656</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Large graphs abound in machine learning, data mining, and several related areas. A useful step towards analyzing such graphs is that of obtaining certain summary statistics - e.g., or the expected length of a shortest path between two nodes, or the expected weight of a minimum spanning tree of the graph, etc. These statistics provide insight into the structure of a graph, and they can help predict global properties of a graph. Motivated thus, we propose to study statistical properties of structured subgraphs (of a given graph), in particular, to estimate the expected objective function value of a combinatorial optimization problem over these subgraphs. The general task is very difficult, if not unsolvable; so for concreteness we describe a more specific statistical estimation problem based on spanning trees. We hope that our position paper encourages others to also study other types of graphical structures for which one can prove nontrivial statistical estimates."]]></description>
<dc:subject>to:NB graph_theory network_data_analysis optimization statistics sra.suvrit</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:6daa880f40eb/</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_theory"/>
	<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:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:sra.suvrit"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1307.7729">
    <title>[1307.7729] Spectral methods for network community detection and graph partitioning</title>
    <dc:date>2013-07-31T13:59:23+00:00</dc:date>
    <link>http://arxiv.org/abs/1307.7729</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We consider three distinct and well studied problems concerning network structure: community detection by modularity maximization, community detection by statistical inference, and normalized-cut graph partitioning. Each of these problems can be tackled using spectral algorithms that make use of the eigenvectors of matrix representations of the network. We show that with certain choices of the free parameters appearing in these spectral algorithms the algorithms for all three problems are, in fact, identical, and hence that, at least within the spectral approximations used here, there is no difference between the modularity- and inference-based community detection methods, or between either and graph partitioning."]]></description>
<dc:subject>heard_the_talk graph_theory community_discovery network_data_analysis spectral_clustering spectral_methods kith_and_kin newman.mark in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:dcb391992efc/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:heard_the_talk"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_theory"/>
	<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:spectral_clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:spectral_methods"/>
	<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:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.win.tue.nl/~rhofstad/NotesRGCN.html">
    <title>Lecture Notes ``Random Graphs and Complex Networks''</title>
    <dc:date>2013-07-21T03:01:00+00:00</dc:date>
    <link>http://www.win.tue.nl/~rhofstad/NotesRGCN.html</link>
    <dc:creator>cshalizi</dc:creator><dc:subject>to:NB books:noted graph_theory networks stochastic_processes network_data_analysis via:arinaldo</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:aab0f559a714/</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:books:noted"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:networks"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:stochastic_processes"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:via:arinaldo"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1307.2302">
    <title>[1307.2302] The blessing of transitivity in sparse and stochastic networks</title>
    <dc:date>2013-07-10T21:34:29+00:00</dc:date>
    <link>http://arxiv.org/abs/1307.2302</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["The interaction between transitivity and sparsity, two common features in empirical networks, implies that there are local regions of large sparse networks that are dense. We call this the blessing of transitivity and it has consequences for both modeling and inference. Extant research suggests that statistical inference for the Stochastic Blockmodel is more difficult when the edges are sparse. However, this conclusion is confounded by the fact that the asymptotic limit in all of the previous studies is not merely sparse, but also non-transitive. To retain transitivity, the blocks cannot grow faster than the expected degree. Thus, in sparse models, the blocks must remain asymptotically small. \n Previous algorithmic research demonstrates that small "local" clusters are more amenable to computation, visualization, and interpretation when compared to "global" graph partitions. This paper provides the first statistical results that demonstrate how these small transitive clusters are also more amenable to statistical estimation. Theorem 2 shows that a "local" clustering algorithm can, with high probability, detect a transitive stochastic block of a fixed size (e.g. 30 nodes) embedded in a large graph. The only constraint on the ambient graph is that it is large and sparse--it could be generated at random or by an adversary--suggesting a theoretical explanation for the robust empirical performance of local clustering algorithms."]]></description>
<dc:subject>graph_theory network_data_analysis community_discovery rohe.karl heard_the_talk in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:aae6fc52830c/</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: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:rohe.karl"/>
	<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: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/1306.3401">
    <title>[1306.3401] Spectral analysis and slow spreading dynamics on complex networks</title>
    <dc:date>2013-06-17T22:34:19+00:00</dc:date>
    <link>http://arxiv.org/abs/1306.3401</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["The Susceptible-Infected-Susceptible (SIS) model is one of the simplest memoryless system for describing information/epidemic spreading phenomena with competing creation and spontaneous annihilation reactions. The effect of quenched disorder on the dynamical behavior has recently been compared to quenched mean-field (QMF) approximations in scale-free networks. QMF can take into account topological heterogeneity and clustering effects of the activity in the steady state by spectral decomposition analysis of the adjacency matrix. Therefore, it can provide predictions on possible rare-region effects, thus on the occurrence of slow dynamics. I compare QMF results of SIS with simulations on various large dimensional graphs. In particular, I show that for Erd\H os-R\'enyi graphs this method predicts correctly the epidemic threshold and the rare-region effects. Griffiths Phases emerge if the graph is fragmented or if we apply strong, exponentially suppressing weighting scheme on the edges. The latter model describes the connection time distributions in the face-to-face experiments. In case of generalized Barab\'asi-Albert type of networks with aging connections strong rare-region effects and numerical evidence for Griffiths Phase dynamics are shown."]]></description>
<dc:subject>graph_spectra graph_theory in_NB epidemics_on_networks</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:0360f85ddcfd/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_spectra"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:epidemics_on_networks"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.jstor.org/stable/10.1086/670300">
    <title>Abstraction and the Organization of Mechanisms</title>
    <dc:date>2013-05-17T02:01:52+00:00</dc:date>
    <link>http://www.jstor.org/stable/10.1086/670300</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Proponents of mechanistic explanation all acknowledge the importance of organization. But they have also tended to emphasize specificity with respect to parts and operations in mechanisms. We argue that in understanding one important mode of organization—patterns of causal connectivity—a successful explanatory strategy abstracts from the specifics of the mechanism and invokes tools such as those of graph theory to explain how mechanisms with a particular mode of connectivity will behave. We discuss the connection between organization, abstraction, and mechanistic explanation and illustrate our claims by looking at an example from recent research on so-called network motifs."

Sentences I never thought I'd write: This paper from _Philosophy of Science_ seems distinctly redundant given the books of Manuel DeLanda.]]></description>
<dc:subject>philosophy_of_science explanation_by_mechanisms graphical_models graph_theory networks abstraction bechtel.william have_read in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:196eada391d9/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:philosophy_of_science"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:explanation_by_mechanisms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graphical_models"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:networks"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:abstraction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:bechtel.william"/>
	<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/1305.3146">
    <title>[1305.3146] Discriminating Power of Centrality Measures</title>
    <dc:date>2013-05-15T15:40:00+00:00</dc:date>
    <link>http://arxiv.org/abs/1305.3146</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["The calculation of centrality measures is common practice in the study of networks, as they attempt to quantify the importance of individual vertices, edges, or other components. Different centralities attempt to measure importance in different ways. In this paper, we examine a conjecture posed by E. Estrada regarding the ability of several measures to distinguish the vertices of networks. Estrada conjectured that if all vertices of a graph have the same subgraph centrality, then all vertices must also have the same degree, eigenvector, closeness, and betweenness centralities. We provide a counterexample for the latter two centrality measures and propose a revised conjecture."]]></description>
<dc:subject>to:NB network_data_analysis graph_theory porter.mason_a.</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:4200a93d49ba/</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:porter.mason_a."/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1304.7528">
    <title>[1304.7528] Semi-supervised Eigenvectors for Large-scale Locally-biased Learning</title>
    <dc:date>2013-05-01T20:26:53+00:00</dc:date>
    <link>http://arxiv.org/abs/1304.7528</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["In many applications, one has side information, e.g., labels that are provided in a semi-supervised manner, about a specific target region of a large data set, and one wants to perform machine learning and data analysis tasks "nearby" that prespecified target region. For example, one might be interested in the clustering structure of a data graph near a prespecified "seed set" of nodes, or one might be interested in finding partitions in an image that are near a prespecified "ground truth" set of pixels. Locally-biased problems of this sort are particularly challenging for popular eigenvector-based machine learning and data analysis tools. At root, the reason is that eigenvectors are inherently global quantities, thus limiting the applicability of eigenvector-based methods in situations where one is interested in very local properties of the data. 
"In this paper, we address this issue by providing a methodology to construct semi-supervised eigenvectors of a graph Laplacian, and we illustrate how these locally-biased eigenvectors can be used to perform locally-biased machine learning. These semi-supervised eigenvectors capture successively-orthogonalized directions of maximum variance, conditioned on being well-correlated with an input seed set of nodes that is assumed to be provided in a semi-supervised manner. We show that these semi-supervised eigenvectors can be computed quickly as the solution to a system of linear equations; and we also describe several variants of our basic method that have improved scaling properties. We provide several empirical examples demonstrating how these semi-supervised eigenvectors can be used to perform locally-biased learning; and we discuss the relationship between our results and recent machine learning algorithms that use global eigenvectors of the graph Laplacian."]]></description>
<dc:subject>to:NB smoothing graph_theory spectral_clustering machine_learning</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:eb304efb82f8/</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:smoothing"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:spectral_clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:machine_learning"/>
</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/1304.1548">
    <title>[1304.1548] Subgraph Frequencies: Mapping the Empirical and Extremal Geography of Large Graph Collections</title>
    <dc:date>2013-04-08T02:08:55+00:00</dc:date>
    <link>http://arxiv.org/abs/1304.1548</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["A growing set of on-line applications are generating data that can be viewed as very large collections of small, dense social graphs -- these range from sets of social groups, events, or collaboration projects to the vast collection of graph neighborhoods in large social networks. A natural question is how to usefully define a domain-independent coordinate system for such a collection of graphs, so that the set of possible structures can be compactly represented and understood within a common space. In this work, we draw on the theory of graph homomorphisms to formulate and analyze such a representation, based on computing the frequencies of small induced subgraphs within each graph. We find that the space of subgraph frequencies is governed both by its combinatorial properties, based on extremal results that constrain all graphs, as well as by its empirical properties, manifested in the way that real social graphs appear to lie near a simple one-dimensional curve through this space. 
"We develop flexible frameworks for studying each of these aspects. For capturing empirical properties, we characterize a simple stochastic generative model, a single-parameter extension of Erdos-Renyi random graphs, whose stationary distribution over subgraphs closely tracks the concentration of the real social graph families. For the extremal properties, we develop a tractable linear program for bounding the feasible space of subgraph frequencies by harnessing a toolkit of known extremal graph theory. Together, these two complementary frameworks shed light on a fundamental question pertaining to social graphs: what properties of social graphs are 'social' properties and what properties are 'graph' properties? 
"We conclude with a brief demonstration of how the coordinate system we examine can also be used to perform classification tasks, distinguishing between social graphs of different origins."]]></description>
<dc:subject>network_data_analysis graph_theory graph_limits kleinberg.jon in_NB ugander.johan backstrom.lars</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:81587f37cc45/</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:graph_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_limits"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:kleinberg.jon"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:ugander.johan"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:backstrom.lars"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.tandfonline.com/doi/abs/10.1080/15427951.2010.557277">
    <title>Taylor &amp; Francis Online :: A Sequential Importance Sampling Algorithm for Generating Random Graphs with Prescribed Degrees - Internet Mathematics - Volume 6, Issue 4</title>
    <dc:date>2013-04-01T19:54:24+00:00</dc:date>
    <link>http://www.tandfonline.com/doi/abs/10.1080/15427951.2010.557277</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Random graphs with given degrees are a natural next step in complexity beyond the Erdős–Rényi model, yet the degree constraint greatly complicates simulation and estimation. We use an extension of a combinatorial characterization due to Erdős and Gallai to develop a sequential algorithm for generating a random labeled graph with a given degree sequence. The algorithm is easy to implement and allows for surprisingly efficient sequential importance sampling. The resulting probabilities are easily computed on the fly, allowing the user to reweight estimators appropriately, in contrast to some ad hoc approaches that generate graphs with the desired degrees but with completely unknown probabilities. Applications are given, including simulating an ecological network and estimating the number of graphs with a given degree sequence."

--- Joe's preprint version from 2006 (!): http://www.people.fas.harvard.edu/~blitz/BlitzsteinDiaconisGraphAlgorithm.pdf]]></description>
<dc:subject>graph_theory graph_sampling blitzstein.joseph diaconis.persi monte_carlo in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:94c28cff2f4a/</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_sampling"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:blitzstein.joseph"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:diaconis.persi"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:monte_carlo"/>
	<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://hal.archives-ouvertes.fr/inria-00630774/">
    <title>HAL :: [inria-00630774, version 1] Metric graph reconstruction from noisy data</title>
    <dc:date>2013-02-28T20:09:26+00:00</dc:date>
    <link>http://hal.archives-ouvertes.fr/inria-00630774/</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Many real-world data sets can be viewed of as noisy samples of special types of metric spaces called metric graphs. Building on the notions of correspondence and Gromov-Hausdorff distance in metric geometry, we describe a model for such data sets as an approximation of an underlying metric graph. We present a novel algorithm that takes as an input such a data set, and outputs the underlying metric graph with guarantees. We also implement the algorithm, and evaluate its performance on a variety of real world data sets."]]></description>
<dc:subject>manifold_learning machine_learning statistics graph_theory in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:478661eac5ef/</dc:identifier>
<taxo:topics><rdf:Bag>	<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:graph_theory"/>
	<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.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://www.cambridge.org/us/knowledge/isbn/item6958599/?site_locale=en_US">
    <title>Graph Spectra for Complex Networks - Academic and Professional Books - Cambridge University Press</title>
    <dc:date>2013-02-17T22:40:06+00:00</dc:date>
    <link>http://www.cambridge.org/us/knowledge/isbn/item6958599/?site_locale=en_US</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Analyzing the behavior of complex networks is an important element in the design of new man-made structures such as communication systems and biologically engineered molecules. Because any complex network can be represented by a graph, and therefore in turn by a matrix, graph theory has become a powerful tool in the investigation of network performance. This self-contained book provides a concise introduction to the theory of graph spectra and its applications to the study of complex networks. Covering a range of types of graphs and topics important to the analysis of complex systems, this guide provides the mathematical foundation needed to understand and apply spectral insight to real-world systems. In particular, the general properties of both the adjacency and Laplacian spectrum of graphs are derived and applied to complex networks. An ideal resource for researchers and students in communications networking as well as in physics and mathematics."

-- After browsing the library copy: disappointing.]]></description>
<dc:subject>books:noted spectral_clustering spectral_methods graph_theory network_data_analysis networks in_NB have_skimmed</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:18254ea690af/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:books:noted"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:spectral_clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:spectral_methods"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:networks"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:have_skimmed"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://pre.aps.org/abstract/PRE/v87/i1/e012803">
    <title>Phys. Rev. E 87, 012803 (2013): Spectra of random graphs with arbitrary expected degrees</title>
    <dc:date>2013-01-10T21:22:50+00:00</dc:date>
    <link>http://pre.aps.org/abstract/PRE/v87/i1/e012803</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We study random graphs with arbitrary distributions of expected degree and derive expressions for the spectra of their adjacency and modularity matrices. We give a complete prescription for calculating the spectra that is exact in the limit of large network size and large vertex degrees. We also study the effect on the spectra of hubs in the network, vertices of unusually high degree, and show that these produce isolated eigenvalues outside the main spectral band, akin to impurity states in condensed matter systems, with accompanying eigenvectors that are strongly localized around the hubs. We give numerical results that confirm our analytic expressions."

- Open version: http://arxiv.org/abs/1306.2507]]></description>
<dc:subject>spectral_clustering graph_theory community_discovery newman.mark kith_and_kin in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:0db555291a9c/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:spectral_clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:community_discovery"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:newman.mark"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:kith_and_kin"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
</rdf:RDF>