Triadic Closure in Configuration Models with Unbounded Degree Fluctuations

The configuration model generates random graphs with any given degree distribution, and thus serves as a null model for scale-free networks with power-law degrees and unbounded degree fluctuations. For this setting, we study the local clustering c(k), i.e., the probability that two neighbors of a degree-k node are neighbors themselves. We show that c(k) progressively falls off with k and the graph size n and eventually for \(k=\varOmega (\sqrt{n})\) settles on a power law \(c(k)\sim n^{5-2\tau }k^{-2(3-\tau )}\) with \(\tau \in (2,3)\) the power-law exponent of the degree distribution. This fall-off has been observed in the majority of real-world networks and signals the presence of modular or hierarchical structure. Our results agree with recent results for the hidden-variable model and also give the expected number of triangles in the configuration model when counting triangles only once despite the presence of multi-edges. We show that only triangles consisting of triplets with uniquely specified degrees contribute to the triangle counting.     

Remarks on the entropy of 3-manifolds

We give a simple combinatoric proof of an exponential upper bound on the number of distinct 3-manifolds that can be constructed by successively identifying nearest neighbour pairs of triangles in the boundary of a simplicial 3-ball and show that all closed simplicial manifolds that can be constructed in this manner are homeomorphic to S3. We discuss the problem of proving that all 3-dimensional simplicial spheres can be obtained by this construction and give an example of a simplicial 3-ball whose boundary triangles can be identified pairwise such that no triangle is identified with any of its neighbours and the resulting 3-dimensional simplicial complex is a simply connected 3-manifold.     

Synchronization in power-law networks

We consider realistic power-law graphs, for which the power-law holds only for a certain range of degrees. We show that synchronizability of such networks depends on the expected average and expected maximum degree. In particular, we find that networks with realistic power-law graphs are less synchronizable than classical random networks. Finally, we consider hybrid graphs, which consist of two parts: a global graph and a local graph. We show that hybrid networks, for which the number of global edges is proportional to the number of total edges, almost surely synchronize.     

n-Particle Quantum Statistics on Graphs

We develop a full characterization of abelian quantum statistics on graphs. We explain how the number of anyon phases is related to connectivity. For 2-connected graphs the independence of quantum statistics with respect to the number of particles is proven. For non-planar 3-connected graphs we identify bosons and fermions as the only possible statistics, whereas for planar 3-connected graphs we show that one anyon phase exists. Our approach also yields an alternative proof of the structure theorem for the first homology group of n-particle graph configuration spaces. Finally, we determine the topological gauge potentials for 2-connected graphs.     

Quantum Ergodicity for Graphs Related to Interval Maps

We prove quantum ergodicity for a family of graphs that are obtained from ergodic one-dimensional maps of an interval using a procedure introduced by Pakónski et al (J. Phys. A, 34, 9303-9317 (2001)). As observables we take the L ² functions on the interval. The proof is based on the periodic orbit expansion of a majorant of the quantum variance. Specifically, given a one-dimensional, Lebesgue-measure-preserving map of an interval, we consider an increasingly refined sequence of partitions of the interval. To this sequence we associate a sequence of graphs, whose directed edges correspond to elements of the partitions and on which the classical dynamics approximates the Perron-Frobenius operator corresponding to the map. We show that, except possibly for subsequences of density 0, the eigenstates of the quantum graphs equidistribute in the limit of large graphs. For a smaller class of observables we also show that the Egorov property, a correspondence between classical and quantum evolution in the semiclassical limit, holds for the quantum graphs in question.     

A new perturbative approximation applied to supersymmetric quantum field theory

We show that a recently proposed graphical perturbative calculational scheme in quantum field theory is consistent with global supersymmetry invariance. We examine a two-dimensional supersymmetric quantum field theory in which we do not know of any other means for doing analytical calculations. We illustrate the power of this new technique by computing the ground-state energy density E to second order in this new perturbation theory. We show that there is a beautiful and delicate cancellation between infinite classes of graphs which leads to the result that E=0.     

Entanglement of one-magnon Schur-Weyl states

We investigate the entanglement properties of symmetry states of the Schur-Weyl duality. Our approach based on reduced two-qubit density matrices, and concurrence as the measure of entanglement. We show that all kinds of “entangled graphs", which describe the entanglement structure in Schur-Weyl states are completely coded in the corresponding Young tableau.     

Roaming moduli space using dynamical triangulations

In critical as well as in non-critical string theory the partition function reduces to an integral over moduli space after integration over matter fields. For non-critical string theory this moduli integrand is known for genus one surfaces. The formalism of dynamical triangulations provides us with a regularization of non-critical string theory. We show how to assign in a simple and geometrical way a moduli parameter to each triangulation. After integrating over possible matter fields we can thus construct the moduli integrand. We show numerically for c=0 and c=−2 non-critical strings that the moduli integrand converges to the known continuum expression when the number of triangles goes to infinity.     

Topological bootstrap theory of hadrons

A topological framework is constructed for anS-matrix bootstrap theory of particles. Each component of anS-matrix topological expansion is associated with a pair of intersecting “quantum” and “classical” surfaces whose complexity exhibits an entropy property. The bounded classical surface embeds graphs that carry the direct observables — energymomentum, spin and electric charge. The closed quantum surface carries a triangulation whose orientations represent internal quantum numbers — which turn out to be baryon number, lepton number and flavor. A form of “color” automatically appears. All strong-interaction components of the expansion are generated through “Landau connected sums” from “zeroentropy” surface pairs — which are self generating. Elementary particles correspond to triangulated areas on the quantum surface; consistency at zero entropy determines allowed hadrondisks on quantum spheres together with the associated quantum numbers. Elementary topological hadrons turn out to include mesons, baryons and baryoniums, with quarks appearing as “peripheral triangles” (along the perimenters of hadron disks) whose attachments correspond to a total of 8 flavors as well as spin. Individual quarks do not carry momentum and cannot be hadrons; quark confinement is automatic. Also appearing within hadron disks are “core triangles” that carry baryon number and electric charge but no flavor or spin. Hadron disks have quantum numbers that accord with the lowestmass physically-observed mesons and baryons. The relation of topological theory to QCD is discussed.     

Low density expansion of the nucleon-nucleus optical-model potential

The optical-model potential for nucleon-nucleus scattering is studied within the framework of the Green function approach to the many-body problem. The optical potential is identified with the self-energy, for which an expansion in terms of irreducible graphs exists. We propose to group the diagrams of this expansion according to the number of independent hole lines and to sum the graphs within each class. This procedure essentially amounts to an expansion in powers of the density and is closely related to the Bethe-Brueckner expansion for the binding energy of nuclear matter. We show that the same convergence parameter appears in both expansions. The one-and two-hole line contributions are studied in detail, numerical estimates are provided and compared with experiment. At low energy, our expansion can be related to the calculation of the optical potential within the framework of nuclear reactions (e.g., using doorway states). At high energy one is led in a natural way to the expressions derived from multiple scattering theory. Thus the hole-line expansion ties together the low and high energy domains of the optical potential. Hole line expansions for the momentum distribution and the total energy are derived from the expansion of the self-energy. The self-consistency requirement is discussed. The present study is restricted to nuclear matter but most results apply to finite nuclei as well.     

Detection of community overlap according to belief propagation and conflict

Most existing methods for detection of community overlap cannot balance efficiency and accuracy for large and densely overlapping networks. To quickly identify overlapping communities for such networks, we propose a new method that uses belief propagation and conflict (PCB) to occupy communities. We first identify triangles with maximal clustering coefficients as seed nodes and sow a new type of belief to the seed nodes. Then the beliefs explore their territory by occupying nodes with high assent ability. The beliefs propagate their strength along the graph to consolidate their territory, and conflict with each other when they encounter the same node simultaneously. Finally, the node membership is judged from the belief vectors. The PCB time complexity is nearly linear and its space complexity is linear. The algorithm was tested in extensive experiments on three real-world social networks and three computer-generated artificial graphs. The experimental results show that PCB is very fast and highly reliable. Tests on real and artificial networks give excellent results compared with three newly proposed overlapping community detection algorithms.     

Homological stabilizer codes

In this paper we define homological stabilizer codes on qubits which encompass codes such as Kitaev’s toric code and the topological color codes. These codes are defined solely by the graphs they reside on. This feature allows us to use properties of topological graph theory to determine the graphs which are suitable as homological stabilizer codes. We then show that all toric codes are equivalent to homological stabilizer codes on 4-valent graphs. We show that the topological color codes and toric codes correspond to two distinct classes of graphs. We define the notion of label set equivalencies and show that under a small set of constraints the only homological stabilizer codes without local logical operators are equivalent to Kitaev’s toric code or to the topological color codes.     

A compact artificial viscosity equivalent to a tensor viscosity

We present a compact artificial viscosity for staggered grid Lagrangian hydrodynamics on polygonal cells in two Cartesian dimensions and using a decomposition into triangles we show that this viscosity is equivalent to a tensor viscosity of Campbell and Shashkov for quadrilaterals.     

表面平整目标的电磁散射快速预估

针对表面基本由平面构成的散射体,在传统弹跳射线法的基础上,对射线跟踪以及射线求交测试方法进行改进,使得该方法对于分析隐身飞行器等有更好的应用。研究了单根射线与三角形的快速求交方法,同时与弹跳射线法相结合,使用三角形对目标进行两次表面拟合,分别得到用于求交测试的稀疏三角面元,以及用于射线追踪的起始三角面元,利用快速求交方法,完成射线追踪,进行物理光学积分,完成目标远场电磁散射的快速预估,将该方法的计算结果与文献结果进行对比,验证了该方法的可靠性,通过计算不同拟合面元密度下情况下的结果,验证了该算法的高效性。     

Coloring random graphs

We study the graph coloring problem over random graphs of finite average connectivity c. Given a number q of available colors, we find that graphs with low connectivity admit almost always a proper coloring, whereas graphs with high connectivity are uncolorable. Depending on q, we find the precise value of the critical average connectivity c(q). Moreover, we show that below c(q) there exists a clustering phase c in [c(d),c(q)] in which ground states spontaneously divide into an exponential number of clusters and where the proliferation of metastable states is responsible for the onset of complexity in local search algorithms.     

Space as a Low-Temperature Regime of Graphs

I define a statistical model of graphs in which 2-dimensional spaces arise at low temperature. The configurations are given by graphs with a fixed number of edges and the Hamiltonian is a simple, local function of the graphs. Simulations show that there is a transition between a low-temperature regime in which the graphs form triangulations of 2-dimensional surfaces and a high-temperature regime, where the surfaces disappear. I use data for the specific heat and other observables to discuss whether this is a phase transition. The surface states are analyzed with regard to topology and defects.     

The number of spanning trees of an infinite family of outerplanar,small-world and self-similar graphs

In this paper we give an exact analytical expression for the number of spanning trees of an infinite family of outerplanar, small-world and self-similar graphs. This number is an important graph invariant related to different topological and dynamic properties of the graph, such as its reliability, synchronization capability and diffusion properties. The calculation of the number of spanning trees is a demanding and difficult task, in particular for large graphs, and thus there is much interest in obtaining closed expressions for relevant infinite graph families. We have also calculated the spanning tree entropy of the graphs which we have compared with those for graphs with the same average degree.     

Network Models in Class C on Arbitrary Graphs

We consider network models of quantum localisation in which a particle with a two-component wave function propagates through the nodes and along the edges of an arbitrary directed graph, subject to a random SU(2) rotation on each edge it traverses. The propagation through each node is specified by an arbitrary but fixed S-matrix. Such networks model localisation problems in class C of the classification of Altland and Zirnbauer [1], and, on suitable graphs, they model the spin quantum Hall transition. We extend the analyses of Gruzberg, Ludwig and Read [5] and of Beamond, Cardy and Chalker [2] to show that, on an arbitrary graph, the mean density of states and the mean conductance may be calculated in terms of observables of a classical history-dependent random walk on the same graph. The transition weights for this process are explicitly related to the elements of the S-matrices. They are correctly normalised but, on graphs with nodes of degree greater than 4, not necessarily non-negative (and therefore interpretable as probabilities) unless a sufficient number of them happen to vanish. Our methods use a supersymmetric path integral formulation of the problem which is completely finite and rigorous.     

Dynamics of entanglement of bosonic modes on symmetric graphs

We investigate the dynamics of an initially disentangled Gaussian state on a general finite symmetric graph. As concrete examples we obtain properties of this dynamics on mean field graphs (also called fully connected or complete graphs) of arbitrary sizes. In the same way that chains can be used for transmitting entanglement by their natural dynamics, these graphs can be used to store entanglement. We also consider two kinds of regular polyhedron which show interesting features of entanglement sharing.