In this paper, we study the existence of perfect matchings and Hamiltonian cycles in the preferential attachment model. In this model, vertices are added to the graph one by one, and each time a new vertex is created it establishes a connection with
Graph symmetries intervene in diverse applications, from enumeration, to graph structure compression, to the discovery of graph dynamics (e.g., node arrival order inference). Whereas Erdős‐Rényi graphs are typically asymmetric, real networks are highly symmetric. So a natural question is whether preferential attachment graphs, where in each step a new node with
 NSFPAR ID:
 10116641
 Publisher / Repository:
 Wiley Blackwell (John Wiley & Sons)
 Date Published:
 Journal Name:
 Random Structures & Algorithms
 Volume:
 55
 Issue:
 3
 ISSN:
 10429832
 Page Range / eLocation ID:
 p. 696718
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Abstract m random vertices selected with probabilities proportional to their current degrees. (Constantm is the only parameter of the model.) We prove that if, then asymptotically almost surely there exists a perfect matching. Moreover, we show that there exists a Hamiltonian cycle asymptotically almost surely, provided that . One difficulty in the analysis comes from the fact that vertices establish connections only with vertices that are “older” (ie, are created earlier in the process). However, the main obstacle arises from the fact that edges in the preferential attachment model are not generated independently. In view of that, we also consider a simpler setting—sometimes called uniform attachment—in which vertices are added one by one and each vertex connects to m older vertices selected uniformly at random and independently of all other choices. We first investigate the existence of perfect matchings and Hamiltonian cycles in the uniform attachment model, and then extend the argument to the preferential attachment version. 
A single experiment is reported that measured the apparent stereoscopic shapes of symmetric and asymmetric objects at different viewing distances. The symmetric stimuli were specifically designed to satisfy the minimal conditions for computing veridical shape from symmetry. That is to say, they depicted complex, bilaterally symmetric, planefaced polyhedra whose symmetry planes were oriented at an angle of 45° relative to the line of sight. The asymmetric stimuli were distorted versions of the symmetric ones in which the 3D position of each vertex was randomly displaced. Prior theoretical analyses have shown that it is mathematically possible to compute the 3D shapes of symmetric stimuli under these conditions, but those algorithms are useless for asymmetric objects. The results revealed that the apparent shapes of both types of objects were expanded or compressed in depth as a function of viewing distance, in exactly the same way as has been reported in many other studies, and that the presence or absence of symmetry had no detectable effect on performance.more » « less

Abstract We focus on the all‐pairs minimum cut (APMC) problem, a graph partitioning problem whose solution requires finding the minimum cut for every pair of nodes in a given graph. While it is solved for undirected graphs, a solution for APMC in directed graphs still requires an
brute force approach. We show that the empirical number of distinct minimum cuts in randomly generated strongly connected directed graphs is proportional toO (n ^{2})n rather than the theoretical value of , suggesting the possibility of an algorithm which finds all minimum cuts in less thann ^{2} time. We also provide an example of the strict upper bound on the number of cuts in graphs with three nodes. We model the distributions with the Generalized extreme value (GEV) distribution and enable the possibility of using a GEV distribution to predict the probability of achieving a certain number of minimum cuts, given the number of nodes and edges. Finally, we contribute to the notion of symmetric cuts by showing that there can beO (n ^{2}) symmetric cuts in graphs when node replication is allowed.O (n ^{2}) 
Without imposing restrictions on a weighted graph’s arc lengths, symmetry structures cannot be expected. But, they exist. To find them, the graphs are decomposed into a component that dictates all closed path properties (e.g., shortest and longest paths), and a superfluous component that can be removed. The simpler remaining graph exposes inherent symmetry structures that form the basis for all closed path properties. For certain asymmetric problems, the symmetry is that of threecycles; for the general undirected setting it is a type of fourcycles; for general directed problems with asymmetric costs, it is a product of three and four cycles. Everything extends immediately to incomplete graphs.more » « less

null (Ed.)Most graph neural network models learn embeddings of nodes in static attributed graphs for predictive analysis. Recent attempts have been made to learn temporal proximity of the nodes. We find that real dynamic attributed graphs exhibit complex phenomenon of coevolution between node attributes and graph structure. Learning node embeddings for forecasting change of node attributes and evolution of graph structure over time remains an open problem. In this work, we present a novel framework called CoEvoGNN for modeling dynamic attributed graph sequence. It preserves the impact of earlier graphs on the current graph by embedding generation through the sequence of attributed graphs. It has a temporal selfattention architecture to model longrange dependencies in the evolution. Moreover, CoEvoGNN optimizes model parameters jointly on two dynamic tasks, attribute inference and link prediction over time. So the model can capture the coevolutionary patterns of attribute change and link formation. This framework can adapt to any graph neural algorithms so we implemented and investigated three methods based on it: CoEvoGCN, CoEvoGAT, and CoEvoSAGE. Experiments demonstrate the framework (and its methods) outperforms strong baseline methods on predicting an entire unseen graph snapshot of personal attributes and interpersonal links in dynamic social graphs and financial graphs.more » « less