skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Phase transitions in the edge/concurrent vertex model
Although it is well known that some exponential family random graph model (ERGM) families exhibit phase transitions (in which small parameter changes lead to qualitative changes in graph structure), the behavior of other models is still poorly understood. Recently, Krivitsky and Morris have reported a previously unobserved phase transition in the edge/concurrent vertex family (a simple starting point for models of sexual contact networks). Here, we examine this phase transition, showing it to be a first-order transition with respect to an order parameter associated with the fraction of concurrent vertices. This transition stems from weak cooperativity in the recruitment of vertices to the concurrent phase, which may not be a desirable property in some applications.  more » « less
Award ID(s):
1361425 1826589
PAR ID:
10184451
Author(s) / Creator(s):
Date Published:
Journal Name:
The Journal of Mathematical Sociology
ISSN:
0022-250X
Page Range / eLocation ID:
1 to 13
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; (, Fundamenta Informaticae)
    ter Beek, Maurice; Koutny, Maciej; Rozenberg, Grzegorz (Ed.)
    For a family of sets we consider elements that belong to the same sets within the family as companions. The global dynamics of a reactions system (as introduced by Ehrenfeucht and Rozenberg) can be represented by a directed graph, called a transition graph, which is uniquely determined by a one-out subgraph, called the 0-context graph. We consider the companion classes of the outsets of a transition graph and introduce a directed multigraph, called an essential motion, whose vertices are such companion classes. We show that all one-out graphs obtained from an essential motion represent 0-context graphs of reactions systems with isomorphic transition graphs. All such 0-context graphs are obtained from one another by swapping the outgoing edges of companion vertices. 
    more » « less
  2. ; ; (, Theoretical Computer Science)
    Doty, David; Spirakis, Paul (Ed.)
    We develop a framework for self-induced phase changes in programmable matter in which a collection of agents with limited computational and communication capabilities can collectively perform appropriate global tasks in response to local stimuli that dynamically appear and disappear. Agents are represented by vertices in a dynamic graph whose edge set changes over time, and stimuli are placed adversarially on the vertices of where each agent is only capable of recognizing a co-located stimulus. Agents communicate via token passing along edges to alert other agents to transition to an Aware state when stimuli are present and an Unaware state when the stimuli disappear. We present an Adaptive Stimuli Algorithm that can handle arbitrary adversarial stimulus dynamics, while an adversary (or the agents themselves) reconfigures the connections (edges) of over time in a controlled way. This algorithm can be used to solve the foraging problem on reconfigurable graphs where, in addition to food sources (stimuli) being discovered, removed, or shifted arbitrarily, we would like the agents to consistently self-organize, using only local interactions, such that if the food remains in a position long enough, the agents transition to a gather phase in which many collectively form a single large component with small perimeter around the food. Alternatively, if no food source has existed recently, the agents should undergo a self-induced collective phase change and switch to a search phase in which they distribute themselves randomly throughout the graph to search for food. Unlike previous approaches to foraging, this process is indefinitely repeatable, withstanding competing broadcast waves of state transition that may interfere with each other. Like a physical phase change, such as the ferromagnetic models underlying the gather and search algorithms used for foraging, microscopic changes in the environment trigger these macroscopic, system-wide transitions as agents share information and respond locally to get the desired collective response. 
    more » « less
  3. ; ; ; ; (, PUMP journal of undergraduate research)
    null (Ed.)
    A prime labeling of a graph G with n vertices is a labeling of the vertices with distinct integers from the set {1,2,...,n} such that the labels of any two adjacent vertices are relatively prime. In this paper, we introduce a snake graph, the fused union of identical cycles, and define a consecutive snake prime labeling for this new family of graphs. We characterize some snake graphs that have a consecutive snake prime labeling and then consider a variation of this labeling. 
    more » « less
  4. ; ; (, Proceedings of the Web Conference 2020 (WWW '20))
    Suppose a graph G is stochastically created by uniformly sampling vertices along a line segment and connecting each pair of vertices with a probability that is a known decreasing function of their distance. We ask if it is possible to reconstruct the actual positions of the vertices in G by only observing the generated unlabeled graph. We study this question for two natural edge probability functions — one where the probability of an edge decays exponentially with the distance and another where this probability decays only linearly. We initiate our study with the weaker goal of recovering only the order in which vertices appear on the line segment. For a segment of length n and a precision parameter δ, we show that for both exponential and linear decay edge probability functions, there is an efficient algorithm that correctly recovers (up to reflection symmetry) the order of all vertices that are at least δ apart, using only ˜ O( n / δ^2) samples (vertices). Building on this result, we then show that O( n^2 log n / δ^2) vertices (samples) are sufficient to additionally recover the location of each vertex on the line to within a precision of δ. We complement this result with an Ω( n^ 1.5 / δ ) lower bound on samples needed for reconstructing positions (even by a computationally unbounded algorithm), showing that the task of recovering positions is information-theoretically harder than recovering the order. We give experimental results showing that our algorithm recovers the positions of almost all points with high accuracy. 
    more » « less
  5. ; ; ; (, Journal of Graph Theory)
    Abstract The ‐deckof an ‐vertex graph is the multiset of subgraphs obtained from it by deleting vertices. A family of ‐vertex graphs is ‐recognizableif every graph having the same ‐deck as a graph in the family is also in the family. We prove that the family of ‐vertex graphs with no cycles is ‐recognizable when (except for ). As a consequence, the family of ‐vertex trees is ‐recognizable when and . It is known that this fails when . 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email