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: Illustrating the importance of edge constraints in backbones of bipartite projections
Bipartite projections (e.g., event co-attendance) are often used to measure unipartite networks of interest (e.g., social interaction). Backbone extraction models can be useful for reducing the noise inherent in bipartite projections. However, these models typically assume that the bipartite edges (e.g., who attended which event) are unconstrained, which may not be true in practice (e.g., a person cannot attend an event held prior to their birth). We illustrate the importance of correctly modeling such edge constraints when extracting backbones, using both synthetic data that varies the number and type of constraints, and empirical data on children’s play groups. We find that failing to impose relevant constraints when the data contain constrained edges can result in the extraction of an inaccurate backbone. Therefore, we recommend that when bipartite data contain constrained edges, backbones be extracted using a model such as the Stochastic Degree Sequence Model with Edge Constraints (SDSM-EC).  more » « less
Award ID(s):
2211744
PAR ID:
10536846
Author(s) / Creator(s):
;
Editor(s):
Papadopoulos, Fragkiskos
Publisher / Repository:
PLOS
Date Published:
Journal Name:
PLOS ONE
Volume:
19
Issue:
5
ISSN:
1932-6203
Page Range / eLocation ID:
e0302973
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. (, PLOS ONE)
    Cherifi, Hocine (Ed.)
    Networks are useful for representing phenomena in a broad range of domains. Although their ability to represent complexity can be a virtue, it is sometimes useful to focus on a simplified network that contains only the most important edges: the backbone. This paper introduces and demonstrates a substantially expanded version of the backbone package for R, which now provides methods for extracting backbones from weighted networks, weighted bipartite projections, and unweighted networks. For each type of network, fully replicable code is presented first for small toy examples, then for complete empirical examples using transportation, political, and social networks. The paper also demonstrates the implications of several issues of statistical inference that arise in backbone extraction. It concludes by briefly reviewing existing applications of backbone extraction using the backbone package, and future directions for research on network backbone extraction. 
    more » « less
  2. ; ; (, Scientific Reports)
    Abstract Projections of bipartite or two-mode networks capture co-occurrences, and are used in diverse fields (e.g., ecology, economics, bibliometrics, politics) to represent unipartite networks. A key challenge in analyzing such networks is determining whether an observed number of co-occurrences between two nodes is significant, and therefore whether an edge exists between them. One approach, the fixed degree sequence model (FDSM), evaluates the significance of an edge’s weight by comparison to a null model in which the degree sequences of the original bipartite network are fixed. Although the FDSM is an intuitive null model, it is computationally expensive because it requires Monte Carlo simulation to estimate each edge’s p value, and therefore is impractical for large projections. In this paper, we explore four potential alternatives to FDSM: fixed fill model, fixed row model, fixed column model, and stochastic degree sequence model (SDSM). We compare these models to FDSM in terms of accuracy, speed, statistical power, similarity, and ability to recover known communities. We find that the computationally-fast SDSM offers a statistically conservative but close approximation of the computationally-impractical FDSM under a wide range of conditions, and that it correctly recovers a known community structure even when the signal is weak. Therefore, although each backbone model may have particular applications, we recommend SDSM for extracting the backbone of bipartite projections when FDSM is impractical. 
    more » « less
  3. ; ; (, PLOS ONE)
    Rozenblat, Celine (Ed.)
    Bipartite projections are used in a wide range of network contexts including politics (bill co-sponsorship), genetics (gene co-expression), economics (executive board co-membership), and innovation (patent co-authorship). However, because bipartite projections are always weighted graphs, which are inherently challenging to analyze and visualize, it is often useful to examine the ‘backbone,’ an unweighted subgraph containing only the most significant edges. In this paper, we introduce the R package backbone for extracting the backbone of weighted bipartite projections, and use bill sponsorship data from the 114 th session of the United States Senate to demonstrate its functionality. 
    more » « less
  4. ; ; (, Proceedings of the ACM on Measurement and Analysis of Computing Systems)
    null (Ed.)
    Applications in cloud platforms motivate the study of efficient load balancing under job-server constraints and server heterogeneity. In this paper, we study load balancing on a bipartite graph where left nodes correspond to job types and right nodes correspond to servers, with each edge indicating that a job type can be served by a server. Thus edges represent locality constraints, i.e., an arbitrary job can only be served at servers which contain certain data and/or machine learning (ML) models. Servers in this system can have heterogeneous service rates. In this setting, we investigate the performance of two policies named Join-the-Fastest-of-the-Shortest-Queue (JFSQ) and Join-the-Fastest-of-the-Idle-Queue (JFIQ), which are simple variants of Join-the-Shortest-Queue and Join-the-Idle-Queue, where ties are broken in favor of the fastest servers. Under a "well-connected'' graph condition, we show that JFSQ and JFIQ are asymptotically optimal in the mean response time when the number of servers goes to infinity. In addition to asymptotic optimality, we also obtain upper bounds on the mean response time for finite-size systems. We further show that the well-connectedness condition can be satisfied by a random bipartite graph construction with relatively sparse connectivity. 
    more » « less
  5. ; ; (, IEEE)
    This paper studies the controllability backbone problem in dynamical networks defined over graphs. The main idea of the controllability backbone is to identify a small subset of edges in a given network such that any subnetwork containing those edges/links has at least the same network controllability as the original network while assuming the same set of input/leader vertices. We consider the strong structural controllability (SSC) in our work, which is useful but computationally challenging. Thus, we utilize two lower bounds on the network’s SSC based on the zero forcing notion and graph distances. We provide algorithms to compute controllability backbones while preserving these lower bounds. We thoroughly analyze the proposed algorithms and compute the number of edges in the controllability backbones. Finally, we compare and numerically evaluate our methods on random graphs. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email