network-science.
60 of 1538 NOTE documents. Back to the full index.
| # | Title | Summary | Status |
|---|---|---|---|
| NOTE-005 v2 | Spectral dimensions of bundled networks | The paper studies a “bundled” network, meaning a fiber graph attached at one node to every node of a base graph, with base and fiber growing with the same length L. For such a network, first-order perturbation theory (SM Eq. 10) gives the low spectrum as λ = ℓ^b/N_f, and from that the gap (“Fiedler”) dimension d_g = 2(d_f,f + d_f,b)/(d_f,f + 2d_f,b/d_g,b), while the spectral dimension stays d_s = d_s,f. The two therefore differ unless d_g,b = 2 or the fiber is finite. For example, the ring-of-rings comb has d_s = 1 but d_g = 4/3, and the 2D-base brush has d_s = 1 but d_g = 2. The rule holds only while the base-induced gap lies below the fiber’s own gap (SM Eq. 14). | Read |
| NOTE-006 v2 | Community Detection on Networks with Ricci Flow | The paper runs Ollivier-Ricci flow w^{(k+1)}{xy} = (1 − κ^{(k)}{xy})·d^{(k)}(x,y) (= W(m_x, m_y)), then cuts edges above a weight threshold. On LFR (n = 500, avg. degree 20) this gives ARI ≈ 1 up to μ ≈ 0.6. On two-block SBM (n = 500, p_intra = 0.15) it gives ≈ 1 up to p_inter/p_intra = 0.5, but it collapses to ≈ 0.1 at 0.55, where Spinglass and Fast Greedy still score ≈ 0.9 and ≈ 0.8. Theorem 4.1 (α = p = 0, cliques G(a,b), a > b ≥ 2) proves in fact only that non-gateway intra-clique edges shrink as (1/a)ⁿ. Gateway intra-clique edges grow at the same rate λ₁ⁿ as inter-community edges, with ratio → k ∈ (0,1). | Read |
| NOTE-026 v2 | Forman-Ricci curvature of networks | The paper specializes Forman’s (2003) Bochner–Weitzenböck curvature on weighted CW complexes to graphs, giving the closed-form edge curvature Ric_F(e) = ω(e)[ω(v1)/ω(e) + ω(v2)/ω(e) − Σ_{e_v1∼e, e_v2∼e}(ω(v1)/√(ω(e)ω(e_v1)) + ω(v2)/√(ω(e)ω(e_v2)))] (Eq. 11). It then proposes three uses: an EMD distance between curvature distributions, which puts Facebook, Google and BioGrid graphs at 0.050–0.060 from a Barabási–Albert model against 0.17–0.36 from Erdős–Rényi and Watts–Strogatz (Table 1); a discrete “2-D-form” Ricci flow γ̃(e) − γ(e) = −Ric_F(γ(e))·γ(e) (Eq. 36) for change detection; and a Laplacian flow ∂G/∂t = (□₁ − F)G (Eq. 45) for denoising. The authors say the flow applications are “only theoretically proposed and illustrated solely on a small example” (§5). | Read |
| NOTE-057 v2 | Networks beyond pairwise interactions (review) | The review sets out the representation hierarchy for group interactions (graph and clique complex, bipartite graph, motifs, simplicial complex, hypergraph) with their operators (incidence, adjacency tensor, boundary B_k, Hodge Laplacian L_k = B_kᵀB_k + B_{k+1}B_{k+1}ᵀ with ker L_k ≅ H_k). It surveys the random models and the dynamics built on them. Its own §V makes the key qualification: linear diffusion with three-body terms “can always be reduced to” a weighted pairwise Laplacian (Eq. 35). A random walk with edge-independent vertex weights is equivalent to one on a weighted projected graph (Chitra–Raphael). Qualitatively new node-level behaviour needs nonlinear group coupling or edge-dependent weights. With those, it reports explosive or abrupt transitions and bistability: Kuramoto with triadic coupling, simplicial SIS with a discontinuous transition, and higher-order ecological models that stabilise coexistence. | Read |
| NOTE-060 v2 | 3rd EEAS report on FIMI threats (2025) | The EEAS classifies channels in foreign information manipulation and interference (FIMI) into four tiers by their tie to a state: official, state-controlled, state-linked (covert, attributed) and state-aligned (non-attributed). It applies the scheme to 505 incidents it detected between 4 Nov 2023 and 4 Nov 2024, involving about 38,000 channels. In a filtered co-involvement graph of 2,055 recurrent channels, 20% are Russian-attributed, 3.5% Chinese-attributed and 76.5% non-attributed. The report states that the sample is illustrative and should not be used to infer general trends. | Read |
| NOTE-075 v2 | Surface optimization in physical networks | The degree counts in Fig. 1d show k = 4 nodes making up 4.6–17.7% of branch points across the six datasets. The pooled 16.6% is 96% human-neuron nodes. Bifurcation angles also fail to peak at 2π/3. From this the authors infer that local branching minimises sleeve surface area under a minimum circumference w, not wire length. For a regular tetrahedron their numerical minimiser merges two bifurcations into a trifurcation at χ = w/r ≈ 0.83, and a thin branch sprouts orthogonally below ρ = w′/w ≈ 0.6. Per-dataset empirical thresholds are ρ_th = 0.52–0.92. The “exact mapping” to string-theory worldsheets covers only the unconstrained minimal-area problem. The SI says the implemented method yields surfaces that are only locally area-minimising (§5). | Read |
| NOTE-083 v2 | Garg & Fetzer, causal claims in economics | GPT-4o-mini is run in nine passes per paper over the first 30 pages of 44,852 NBER/CEPR working papers. Edges kept in at least 4 of 9 passes, JEL-mapped, give “claim graphs” in which the share of edges backed by DiD/IV/RCT/RDD/synthetic control rises from 7.7% (1990) to 31.7% (2020). In year-fixed-effect-only regressions, doubling causal edges is associated with +1.36 pp top-five probability and +11.2% citations, while non-causal counterparts are flat or negative. The validation checks paper-level method labels, and only weakly: RCT and field labels have precision ≤ 0.10. It never checks the edges themselves against human labels. | Read |
| NOTE-085 v2 | Local separators and community structure | This is a comparison of the authors’ local 1- and 2-separator decompositions against Infomap, Label Propagation, Leiden and Louvain (igraph) on five sparse graphs (62 to 9,133 nodes). Local separators score lower overlapping modularity than the modularity optimisers everywhere, and lower than Infomap on 3 of 5 graphs (Table 2). Their edge is confined to high density thresholds on the two road networks, where the best radius gives a handful more qualifying clusters: about 12 against about 5 at β ≥ 1.25 on Euroroads, and about 50 against about 40 for Infomap at β ≥ 1.5 on NRW (Figs. 3–4). On Netscience all methods are similar. At δ = 1 on both road networks, and at δ = 1.25 on NRW, Infomap yields more qualifying clusters than any local-separator setting. | Read |
| NOTE-153 v2 | Rizi — What is emergence, after all? | A perspective, not an argument with results. Rizi proposes that emergence is present when a many-to-one coarse-graining F (Eq. 1, N′ < N) keeps the macro description predictive after most micro detail is discarded. He says the onset of emergence is located by order parameters, diverging susceptibility and correlation length, and RG fixed points, and that dualities show macro behaviour is not dictated by micro “stuff”. Herd immunity on networks (percolation, the S–R interface density ρ_SR) is offered as a social case. The paper then asserts that science needs only weak emergence, and that invoking strong emergence “steps outside the scope of scientific method”. | Read |
| NOTE-435 | A Network Theory of Mental Disorders | Borsboom states the network theory as five principles: complexity, symptom-component correspondence, direct causal connections between symptoms, disorders as tightly coupled symptom clusters, and hysteresis. Disorder is an alternative stable state of a strongly connected network that outlasts its trigger; health is the stable state of a weakly connected one. Treatment is symptom, external-field or network intervention. The evidence offered is indirect, and the theory is presented as an organizing framework, not a fitted model. | Read |
| NOTE-494 | Cross-region neuron co-firing mediated by ripple oscillations | In 35 patients (43 sessions, 1,373 units) doing a Sternberg task, ripple co-occurrence between bundles is about 5% at every distance from 71 to 223 mm, and unit pairs co-fire a median 34% more during co-ripples than in no-ripple periods (n = 31,489 pairs), 117% more by rate-corrected STTC. Load 3 raises co-ripple co-firing 13% (maintenance) and 19% (retrieval) over load 1. Encoding co-firing recurs at retrieval in 0.29% of cell-pair trials in co-ripples versus 0.14% outside them, 0.36% versus 0.23% for fast versus slow load 3 responses. | Read |
| NOTE-529 | Unveiling Mode Connectivity in Graph Neural Networks | GCN node-classification solutions from different seeds show linear loss barriers that vary by graph (small on Cora, Citeseer; large on Coauthor-CS, Squirrel) and vanish along fitted quadratic Bezier curves. GCN, GraphSAGE and GAT give similar barriers, MLPs different ones. On CSBM graphs barriers fall with density and feature separability and peak at middling homophily. Stated without proof: a barrier bound through the spectral gap, a generalisation bound proportional to the barrier, and a Wasserstein distance between graphs’ interpolation-loss curves that bounds the domain-adaptation gap. | Read |
| NOTE-559 | In Epistemic Networks, Is Less Really More? | Over a wider parameter space than Zollman used, the advantage of sparse networks vanishes when the better option is even slightly better, when groups are larger, or when agents gather more data per round. It survives only where inquiry is hard, and Kummerfeld and Zollman’s effects behave the same way. Transient diversity is the robust lesson. | Read |
| NOTE-564 | The Epistemic Benefit of Transient Diversity | A bandit model with beta priors. Sparse networks beat dense ones, as in 2007, but extreme priors reverse the order, and sparse networks of dogmatic agents often never converge. Limited information and dogmatism each sustain diversity, and together sustain it too long. What communities need is diversity that is transient. | Read |
| NOTE-567 | Network Epistemology: Communication in Epistemic Communities | A survey. The best communication structure depends on the epistemic problem: transmission of costly information favours minimal or star networks, pooling of estimates favours regular ones (denser is faster), and learning by trying favours sparse ones. Intuitions that a group communicates too little or is too centralised are often wrong. | Read |
| NOTE-574 | Experimentation by Industrial Selection | Uses the antiarrhythmic drug disaster and a modified Zollman bandit model to show that industry can bias a scientific community of honest Bayesian agents by funding those whose methods already favour its product, given methodological diversity, merit-based influence and turnover. A merit-based independent funder makes this worse; one that discounts industry-funded work counteracts it. Integrity safeguards do not touch the mechanism. | Read |
| NOTE-583 | The Communication Structure of Epistemic Communities | Simulations of Bala and Goyal’s bandit model on small networks. Cycles learn the better action more reliably than wheels or complete graphs, and more slowly. Over every network of up to six agents, density and clustering predict failure, and centrality does not. The cause is that dense networks spread an early unlucky run to everyone before diversity can correct it. | Read |
| NOTE-655 | Irreversibility in bacterial regulatory networks | In an ensemble of sign-consistent Boolean rules on the 87-gene core of the E. coli regulatory network, 51 genes admit a transient knockout or overexpression that leaves the network in a different attractor; only genes that reach a positive circuit can, and the likelihood grows with the weighted number of paths to one. Transitions run from small basins to large. The comparison with evolved crp-knockout strains supports the network’s sign structure strongly and its irreversibility predictions only weakly; no transient perturbation was done in cells. | Read |
| NOTE-669 | Hyperbolic Representation Learning: Revisiting and Advancing | Shows, by tracking each node’s hyperbolic distance to the origin, that hyperbolic graph models trained on task losses do not by themselves place a tree’s root nearest the origin or spread its levels outward: on synthetic 3-ary trees the root sits well off the minimum and level order is recovered for only 69–75% of node pairs. A centroid recentring plus an outward-push loss (HIE), using no level information, raises this to 75–84% and improves link prediction and node classification, most on the least tree-like graphs. | Read |
| NOTE-673 | Multiscale unfolding of real networks by geometric renormalization | Defines a renormalization group for networks embedded in the S¹ hidden metric space: merge blocks of angular neighbours, link supernodes if any members were linked. To first order the S¹ model maps into itself (κ′ = (Σκ^β)^{1/β}, β fixed, μ and R over r), so layers are the same ensemble with ⟨k⟩ scaled by r^ν, ν = 2/(γ−1) − 1 or 2/β − 1. Six real networks collapse across layers by eye and keep their communities; downscaled replicas reproduce three dynamics, and multiscale greedy routing succeeds more often. | Read |
| NOTE-678 | Emergent Hyperbolic Network Geometry | Shows that simplicial complexes grown by gluing d-simplices to (d − 1)-faces, by a rule with no geometry in it, have exponential or power-law degrees (γ = 2 + 1/(d + s − 1)) by a master equation, high clustering and modularity, and a tree as their dual; and draws them, with all links of equal length, as ideal simplices tiling the Poincaré ball. The hyperbolicity is that drawing, which the authors say depends on the equal-length assumption; it is not measured or proved. A fitness on faces gives a simulated transition to growth in one direction. | Read |
| NOTE-680 | Hyperbolic Geometry of Complex Networks | Shows, for a model in which nodes sit in a hyperbolic disk and connect with a Fermi–Dirac probability of their hyperbolic distance, that the degree distribution is a power law with γ = 2α/ζ + 1 and that clustering is set by a temperature, strongest at T = 0 and gone above T = 1; that a circle-similarity model with power-law hidden degrees is the same ensemble once degree is read as radial depth; and that the configuration model and Erdős–Rényi graphs are its limits with the angular, metric part of the distance removed. Greedy routing by the coordinates is near-optimal and robust in its networks. No real network is embedded. | Read |
| NOTE-775 | Pecora et al. — Cluster synchronization and isolated desynchronization | For identical units with identical, symmetric couplings, the orbits of the coupling graph’s automorphism group are clusters that can each be exactly synchronized. An irreducible-representation change of coordinates block-diagonalizes the variational equations, so each cluster’s stability is computed separately. When the group splits as a direct product, a cluster moved by one factor can lose synchrony while the others keep it. An 11-node electro-optic network showed this as predicted. | Read |
| NOTE-810 | Vilone and Polizzi — Opinion misperception and the emergence of silence | In two agent-based models on scale-free networks, agents’ private beliefs are fixed and only what they say changes. A small hard-core minority placed on nodes of a chosen degree makes the expressed and locally perceived opinion far more minority-leaning than the beliefs, mainly by driving 55–60% of agents, almost all of the majority, into silence. The network’s direct effect on perception is small and not even of constant sign. Simulation only, with no empirical validation. | Read |
| NOTE-814 | Salter-Duke — Tangled webs | An exact but exponential algorithm finds edge-connectivity tangles in graphs of up to about 200 vertices. On eleven small real networks, tangle communities resemble those of standard methods only where community structure is strongly delineated; three networks have no distinguishable tangles at the orders reached, and where tangles do distinguish regions, some hold only one to three vertices. On images, lines one pixel wide cannot be distinguished. The author concludes the tangle notion of cohesion “is not as compelling as I had hoped”. | Read |
| NOTE-840 | Golub & Jackson — Naïve Learning in Social Networks and the Wisdom of Crowds | Agents get independent signals with mean μ and repeatedly replace their beliefs by fixed weighted averages of their neighbours’ (DeGroot). In a convergent network the consensus is s·p(0), with s the unit left eigenvector of the interaction matrix, and a growing society’s limits converge in probability to μ if and only if the largest influence weight tends to zero (Proposition 2). With reciprocal, equal weights this is maximum degree over total degree → 0. A finite group that everyone attends to blocks it; balance plus minimal out- or in-dispersion guarantee it. How fast consensus is reached is unrelated to whether it is right. | Read |
| NOTE-916 | Malkov & Yashunin — Hierarchical navigable small world graphs for approximate nearest neighbour search | HNSW is a stack of proximity graphs on nested random subsets of the data. Each element’s top layer is drawn from a geometric distribution, and new neighbours are chosen by a pruning rule that favours diverse directions. Searching from the sparse top layer down makes per-query cost grow about logarithmically with N on uniform random data in 4 and 8 dimensions, which flat NSW graphs did not. The logarithmic bound is derived only for exact Delaunay graphs of bounded mean degree, which HNSW does not build. For the graphs it does build, logarithmic scaling is measured, at low dimension only, and on 200M SIFT vectors the paper reports the scaling “deviates from the pure logarithm”. The neighbour-selection rule is what keeps clustered data searchable: in the paper’s synthetic test with 100 isolated clusters, linking each element to its nearest neighbours fails to reach high recall. There is no worst-case or recall guarantee, no deletion, and no analysis of query distributions unlike the data. | Read |
| NOTE-923 | Kleinberg — The small-world phenomenon: an algorithmic perspective | On an n × n lattice where each node also gets q long-range links drawn with probability proportional to d^(−r), short paths exist for r = 0, but no algorithm that sees only the links of nodes the message has visited finds them faster than about n^(2/3) steps in expectation. At r = 2 the greedy rule (pass to the contact nearest the target in lattice distance) delivers in O((log n)²) expected steps (proved for p = q = 1); for 0 ≤ r < 2 every such algorithm needs Ω(n^((2−r)/3)) and for r > 2 Ω(n^((r−2)/(r−1))). So efficient decentralized search depends on how the long-range links are distributed relative to the lattice, not on the links’ existence or on the graph’s diameter. The k-dimensional version (r = k) is stated without proof, and the model is a lattice with a known distance that every node can compute to the target. | Read |
| NOTE-1010 | Random Hyperbolic Graphs: Degree Sequence and Clustering | Proves for the threshold hyperbolic random graph (curvature −1, density exponent α > 1/2, R = 2 log n + C) that the average local clustering coefficient is Θ(1) with high probability and that the degree sequence is a power law with exponent 2α + 1 up to the maximum degree n^(1/(2α)+o(1)), with exact asymptotics for the fraction of each degree. Skimmed: the statements and the method were read, the proofs only in outline. | Skimmed |
| NOTE-1011 | Clustering and the hyperbolic geometry of complex networks | For Krioukov et al.’s hyperbolic random graph with 0 < ζ/α < 2, proves that below temperature 1 (β > 1) the global clustering coefficient converges to an explicit positive constant when ζ/α < 1 and to zero when 1 ≤ ζ/α < 2, and that at or above temperature 1 it converges to zero; clustering among vertices of bounded type stays positive for all ζ/α < 2 when β > 1. Skimmed: §1 and the theorem statements read, the proofs not. | Skimmed |
| NOTE-1038 | Weatherall, O’Connor and Bruner — How to beat science and influence people | In Bala–Goyal network models with Bayesian policy makers who do not gather evidence, a propagandist who forwards only the real results of unbiased scientists that happen to favour the worse action, or who runs honest studies and publishes only the unfavourable ones, can leave policy makers near-certain of the false theory while the scientists converge on the true one. It works best when the problem is hard, studies are small, scientists are many and policy makers hear few of them. A journalist who reports one result for each side every round slows policy makers’ learning and never helps it. | Read |
| NOTE-1085 | Lerman, Yan & Wu — The majority illusion in social networks | A sampling fact about networks, not a finding about people: when an attribute is correlated with degree, the share of nodes that see it in a majority of their neighbours can far exceed its global share (60–80% of nodes when 5% hold it, in a heavy-tailed synthetic network), and more so in disassortative networks. A binomial model from the joint degree distribution predicts the share. No person’s belief or behaviour is measured, and the attributes on the real networks are assigned, not observed. | Read |
| NOTE-1098 | Toward an integrative psychometric model of emotions | An integrative psychometric model of emotions must allow distinct emotions, variation between and within persons, and causal relations among components, one property from each broad class of emotion theory. Reflective and formative latent-variable models fail. A network model passes. In it, the network of causally interacting components constitutes the emotion, and a distinct emotion is a weakly emergent small-world community. Strong connectivity predicts self-sustaining activation and hysteresis, hence longer emotions. A programme paper: no data, and limits named candidly. | Read |
| NOTE-1099 | Statistical ranking and combinatorial Hodge theory | Rank aggregation as combinatorial Hodge theory. Aggregated pairwise comparisons form an edge flow, and its orthogonal decomposition gives a least-squares global ranking (the gradient), local inconsistency (curl) and global inconsistency (harmonic). The size of the cyclic residual certifies whether any global ranking is meaningful. The framework is cardinal, generalizes Borda, and is not Kemeny. | Read |
| NOTE-1116 | Flows and Decompositions of Games: Harmonic and Potential Games | A finite game is read as a flow, the unilateral payoff differences on the graph of strategy profiles, and the Helmholtz decomposition of that flow splits the game uniquely into potential, harmonic and nonstrategic parts. Potential games are those with no harmonic part. Harmonic games, the pure-conflict part, generically have no pure equilibrium. The nearest potential game is a closed-form l2 projection. | Read |
| NOTE-1126 | Friedkin, Jia & Bullo — A theory of the evolution of social power | A Friedkin–Johnsen model of opinion change on each issue, with a reflection mechanism between issues: a member’s closure to influence on the next issue equals their influence centrality on the last. In simulation it drives one member to full closure and the rest to full openness. In 30 four-person student groups discussing 15 choice dilemmas, prior centrality predicted next-issue closure, more strongly along the sequence; influence networks thinned and discussions shortened. The rate of consensus did not change. | Read |
| NOTE-1135 | Jia, MirTabatabaei, Friedkin & Bullo — Opinion dynamics and the evolution of social power in influence networks | DeGroot averaging on each issue, and between issues each member’s self-weight is set to their share of control over the last consensus. With a fixed, strongly connected matrix of relative interpersonal weights, self-weights converge from every non-autocratic start to a unique equilibrium fixed by the eigenvector centralities: power ranks as centrality, accumulates at the top, is autocratic exactly for a star network and democratic exactly for a doubly stochastic one. Members whom no path reaches end with no power. | Read |
| NOTE-1157 | DeGroot — Reaching a consensus | A group whose members each replace their opinion, over and over, by a fixed weighted average of everyone’s current opinions, F⁽ⁿ⁾ = PⁿF, is a Markov chain run on opinions. It reaches a consensus from every start exactly when the chain has one closed class and that class is aperiodic. The consensus is then a linear opinion pool whose weights are the chain’s stationary vector, which gives members outside the closed class no weight. Two closed classes, or one periodic class, give no consensus. The weights are fixed, and nothing in the model tracks the truth. | Read |
| NOTE-1179 | Airoldi, Blei, Fienberg and Xing — Mixed membership stochastic blockmodels | Each node has a Dirichlet membership vector over K blocks; for every ordered pair, each node draws one block for that interaction, and the edge is Bernoulli with the block pair’s rate in B, scaled by a sparsity factor. So a node can take different roles with different partners. Variational EM with a nested schedule fits it. It recovers simulated blocks, matches 63 of 69 students to their grades, and maps yeast proteins to functions at about 87% against a 70% baseline. Its claim that B and the memberships do not compete for the data is asserted, not shown: memberships and B trade along a continuum given the graph, and the sparsity factor is exactly confounded with B’s scale. | Read |
| NOTE-1217 | Stewart, Golubitsky & Pivato — Symmetry groupoids and patterns of synchrony | In a coupled cell network, an equivalence relation on the cells gives a synchrony subspace invariant under every vector field the network admits if and only if it is balanced: every two equivalent cells have an input isomorphism that maps each input to an equivalent one (Theorem 6.5). Symmetry is one source of balance, not the only one, so robust synchrony occurs in networks with no symmetry. The dynamics on such a subspace are admissible for a smaller quotient network (Theorem 9.2), which can have a symmetry the original lacks. The paper treats existence only, not stability, and says so. | Read |
| NOTE-1218 | Torres-Hugas et al. — Cycle holonomy and remote synchronization | For a phase model whose edges carry antisymmetric phase lags, the twisted Laplacian Lα = δα*δα has a zero mode exactly when every cycle holonomy is 0 mod 2π, and otherwise its smallest eigenvalue measures the residual incompatibility; for an isolated ℓ-cycle that eigenvalue is largest at holonomy π. The symmetric Sakaguchi–Kuramoto model is a different model, but on cactus graphs its lag gives each ℓ-cycle a path mismatch (ℓ − 2)α, which an associated connection is built to carry as holonomy. In the triangle–pentagon remote-synchronization motif, the pentagon’s mismatch reaches π at α = π/3, where the locked branch is exactly a two-group state; but the branch has already lost transverse stability at αc ≈ 1.0164, so the holonomy marks geometry, not stability. | Read |
| NOTE-1222 | Hansen & Ghrist — Opinion dynamics on discourse sheaves | A discourse sheaf gives each agent a private opinion space and each edge a discourse space, with a linear expression map from each agent into each of its edges. Opinion diffusion by the sheaf Laplacian converges to the projection onto the global sections: agreement in what neighbours express, not in what they hold. Letting the expression maps diffuse instead converges to the nearest sheaf in which the fixed opinions agree in expression, which the authors call “learning to lie”. Nothing in the dynamics checks expression against what is held, so the agreement reached is coherence, not accuracy. | Read |
| NOTE-1224 | Singer — Angular synchronization | Angles θ₁, …, θₙ are estimated, up to one global phase, from noisy offsets θᵢ − θⱼ of which an unknown fraction are pure outliers, by the top eigenvector of the Hermitian matrix Hᵢⱼ = e^{iδᵢⱼ} or by an SDP like Goemans–Williamson’s. On the complete graph a random-matrix argument puts the eigenvector’s threshold at p > 1/√n good offsets, with the expected squared correlation near 1/(1 + 1/(np²)). Fano’s inequality shows no algorithm can do much better: the information bound is of order √(n/m), and the polynomial method’s threshold is within a factor √((L − 1)/(2 log₂ L)) of it, where 2π/L is the angular resolution, while exhaustive maximum likelihood costs O(mLⁿ). | Read |
| NOTE-1233 | Hansen & Ghrist — Toward a spectral theory of cellular sheaves | An exploratory programme, not a single result: the Hodge Laplacian of a weighted cellular sheaf, whose kernel in degree k is the cohomology H^k (in degree 0, the global sections), with sheaf versions of spectral graph theory’s basics: harmonic extension, an eigenvalue bound for normalized sheaves, interlacing, pushforward and covering spectra, product spectra, effective resistance and a sparsification theorem. The heat flow ẋ = −Δ^k x converges exponentially to the orthogonal projection onto the harmonic cochains (Prop. 8.1). Kron reduction fails for general sheaves, because an interior vertex can impose constraints on the boundary that no pairwise sheaf expresses. A Cheeger inequality is not proved; the applications in §8 are sketches. | Read |
| NOTE-1327 | Yu et al. — AvAtar active OT alignment | For alignment by entropic optimal transport, AvAtar picks which source objects to send to an oracle, who names each one’s true match. It scores a candidate by the derivative of a proxy utility of the transport plan (how near a permutation, or how consistent with the graphs, the plan is) with respect to supervising each possible match, averaged over matches by the current plan. The derivative is exact, from one singular positive semidefinite linear system solved by conjugate gradients. At a fixed budget of 20% extra labels on top of 20% given, it beats uncertainty baselines by up to 2.8 MRR points and random choice by up to 16, without variances reported. | Read |
| NOTE-1328 | Vayer et al. — Fused Gromov–Wasserstein | FGW compares two attributed graphs with one coupling whose cost mixes, with weight α, a Wasserstein term on node features and a Gromov–Wasserstein term on structure. For α in (0, 1), q = 1 and distance-matrix structures it is a metric that vanishes exactly when a bijection preserves weights, features and structure. As α tends to 0 or 1 it tends to W or GW. On benchmark graph classification it is competitive with graph kernels, but the supplement shows Wasserstein on features alone matching or beating it on several datasets. | Read |
| NOTE-1330 | Chowdhury & Mémoli — Network Gromov–Wasserstein | The Gromov–Wasserstein distance, defined by minimizing the distortion of a coupling, is a pseudometric on all measure networks: any Polish node set with a probability measure and any bounded, possibly asymmetric, edge-weight function. It is zero exactly when the two networks are weakly isomorphic, that is, when both are images of one network that preserves weights and measures. Cheap invariants give a hierarchy of lower bounds, and the third lower bound, a transport problem whose costs are themselves transport problems, reduces to one-dimensional transport in closed form. The bounds are one-sided: networks can agree on every invariant and still be apart. | Read |
| NOTE-1331 | Sarkar, Mukherjee and Sato — Attention as lattice gauge theory | Under per-entity O(d) frame freedom, transports carry invariant information only around cycles, a triangle’s invariants are class functions of its holonomy, and an equivariant edge update is Ψ(H)Tᵢⱼ with Ψ conjugation-equivariant: a sound conditional theorem, standard in lattice gauge theory and synchronization, whose “unique form” is a family. The untrained S4 experiments show composition doing the work and Wilson-loop routing adding 0.6–7.8 points; the 0.99 AUC is a ceiling the data’s construction sets, as the paper itself computes. | Read |
| NOTE-1332 | Bodnar et al. — Neural sheaf diffusion | Bodnar et al. read sheaf diffusion on a graph as a projection onto the harmonic space of a sheaf Laplacian and ask which classes of restriction maps can make that projection linearly separate a node labelling. A symmetric one-dimensional sheaf, which is a weighted graph Laplacian, cannot separate the two sides of a balanced bipartite graph; signed maps separate any two classes; no one-dimensional sheaf separates three; diagonal maps with d ≥ C stalks, and O(d) bundles for C ≤ 2d at d = 2 and 4, separate any number. Every one of these sheaves is built from the labels. Learned from features, such sheaves give competitive node classification on six small heterophilic benchmarks. The claim that the O(d) construction exists only at d = 2 and 4 is wrong: it works at d = 8 too. | Read |
| NOTE-1334 v2 | Zeng et al. — HOT multi-network alignment | Aligns K networks at once by one multi-marginal coupling tensor. The networks are first co-clustered through a fused Gromov–Wasserstein barycenter, then each cluster’s nodes are aligned by multi-marginal fused GW with a cost from anchor-based random-walk embeddings, solved by a KL proximal point method. The joint objective at any tensor is the sum of the pairwise objectives at its marginals, so it bounds the sum of pairwise optima from above. On three-network benchmarks whose true correspondences are consistent by construction, it beats pairwise and multi-network baselines in pairwise and high-order hits; no experiment isolates the joint coupling from the new cost and the clustering. | Read |
| NOTE-1354 v2 | Škorić, de Hoogh and Zannone — Evidence-based subjective logic | Subjective logic’s discounting x ⊗ y multiplies opinions and does not distribute over its evidence-adding consensus ⊕, so trust networks must be put in a canonical form, often by discarding edges, to avoid double-counting. EBSL replaces it with x ⊡ y = g(x)·y, a scalar multiple of y’s evidence, which distributes over ⊕; the recursive, PageRank-like fixed point R = A ⊕ (offdiag R ⊡ A) then handles loops without discarding anything, and on Tribler data it converges in 9–47 iterations. There is no ground truth; robustness to self-promotion, slander and Sybil attacks is left for future work. | Read |
| NOTE-1356 | Castro and Liskov — Practical Byzantine fault tolerance | A state-machine replication protocol that keeps safety with at most ⌊(n − 1)/3⌋ arbitrarily faulty replicas and no timing assumption, needing weak synchrony only for liveness; a three-phase commit within views and a view change that carries prepared requests forward. With MACs in place of signatures, a replicated NFS ran the Andrew benchmark 3% slower than Digital Unix’s NFS on four replicas, with view changes not yet implemented in the measured library. | Read |
| NOTE-1374 | Friedkin — A formal theory of reflected appraisals in the evolution of power | Friedkin extends the Friedkin–Johnsen influence model across a sequence of issues: each member’s self-weight on the next issue is set to their average total control over the last. In 50 four-person laboratory groups, prior control predicts the next self-weight. In 100,000 simulated random networks, over 98% evolve to one leader whose uninfluenced preference settles every issue through intermediaries. A re-run reproduces this, and shows that the DeGroot–Friedkin version of LIT-1146 does not concentrate power on the same networks. | Read |
| NOTE-1381 | Halpern and Moses — Knowledge and common knowledge in a distributed environment | Defines distributed, someone-, everyone- and common knowledge for processors in a system of runs, and shows that a guaranteed coordinated attack makes the attack common knowledge (Proposition 4), while over a channel that may lose any message nothing becomes common knowledge that would not be common knowledge with no messages delivered (Theorem 5), so no correct protocol ever attacks (Corollary 6). Temporal imprecision alone, uncertain start times and delivery times, makes common knowledge unattainable (Theorem 8). Weaker fixed-point variants (ε-, eventual and timestamped common knowledge) are attainable in many systems. | Read |
| NOTE-1385 | Holme and Newman — Coevolution of networks and opinions | N agents with G = N/γ possible opinions on a random graph; at each step a random agent either moves one of its edges to a random holder of its own opinion (probability φ) or copies a random neighbour’s opinion (1 − φ). The process always ends in disconnected communities each of one opinion. For k̄ = 4 and γ = 10 a continuous transition at φ_c = 0.458 ± 0.008 separates a giant like-minded community plus small ones (φ < φ_c) from only small communities of mean size about γ (φ > φ_c), with exponents a = 0.61, b = 0.7 and z = 0.61 outside the percolation class. Simulation only. | Read |
| NOTE-1392 | DeMarzo, Vayanos and Zwiebel — Persuasion bias, social influence, and unidimensional opinions | Agents average the reports of those they listen to with fixed relative weights, treating every round’s report as new (persuasion bias, a DeGroot model). In a strongly connected network they reach a consensus weighted by the stationary distribution of the listening matrix, so influence comes from network position as well as precision; the consensus is correct only in “balanced” networks, and fully rational agents who know the network reach the correct beliefs in at most N² rounds. Long-run differences of opinion line up along one line given by the second eigenvectors, across every issue. | Read |
| NOTE-1394 v2 | Gross and Blasius — Adaptive coevolutionary networks | Reviews models, mostly 1998–2007, in which a network’s topology and its nodes’ states change each other, and names four recurrent outcomes: robust self-organization toward critical states (Bornholdt and Rohlf’s threshold networks reach K = 2), spontaneous “division of labour” into classes of nodes (Ito and Kaneko), complex topologies from local rules, and new system-level dynamics such as bistability and oscillation in an adaptive SIS epidemic. A sketch, not a theory: the mechanisms are argued from examples, and its summary of Holme and Newman inverts the model’s parameter. | Read |
| NOTE-1403 | Kleinman, Liu and Redding — International friends and enemies | A country’s real-income elasticity to a partner’s productivity, from a constant-elasticity trade model with input-output links, predicts political alignment with that partner. Instrumented by a counterfactual Chinese productivity shock from the 1980 equilibrium (119 countries, 1980–2010) or by air-versus-sea distance (pairs, 1970–2012), it moves UN voting similarity (0.094 SD per SD in the panel), lowers strategic rivalry, and raises formal alliances. The paper’s own model is strategic: alignment is a costly action a country takes to raise a partner on whom its income depends. | Read |
| NOTE-1410 | Akkoyunlu, Ekanadham and Huber — Some constraints and tradeoffs in the design of network communications | A design paper on interprocess communication in networks of sequential processes: complete status of a transaction is impossible in an arbitrary distributed facility and, with time-outs, even in a reliable one, and the insertion property forces the system to withhold status. Its Appendix states, as a story of gangsters and a messenger who may be mugged, that no finite exchange over a lossy channel brings two parties to know they agree a message got through, with a shortest-sequence proof. That is the coordinated attack problem in substance, three years before Gray (1978), framed as mutual knowledge of delivery. | Read |
| NOTE-1414 | Ito and Kaneko — Spontaneous structure formation in a network of chaotic units | In a globally coupled logistic map whose units each renormalize their incoming weights after strengthening those from units in similar states, identical units split, in the desynchronized high-turnover regime, into a persistent core that the others attend to and a periphery the core ignores; the split needs states and weights to act on each other. Simulation only, N = 100, one parameter point in detail. | Read |