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: The Idemetric Property: When Most Distances Are (Almost) the Same
This paper introduces the idemetric property, which formalizes the idea that, in many social and information networks, most nodes have similar distances between them. The paper shows that samples from standard generative models (preferential attachment, etc.) are idemetric in our sense. The paper also considers algorithmic applications. For example, we prove that a single breadth-first search provides a solution to the all-pairs shortest paths problem, so long as one is prepared to accept paths which are of stretch close to 2 with high probability.  more » « less
Award ID(s):
1813188
PAR ID:
10096616
Author(s) / Creator(s):
; ; ; ; ; ;
Date Published:
Journal Name:
Proceedings of the Royal Society of London. Series A, Mathematical and physical sciences
ISSN:
0080-4630
Page Range / eLocation ID:
475(2222)
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; ; ; ; (, Proceedings of the 2020 International Design Engineering Conferences)
    null (Ed.)
    Abstract We demonstrate analytically that it is possible to construct a developable mechanism on a cone that has rigid motion. We solve for the paths of rigid motion and analyze the properties of this motion. In particular, we provide an analytical method for predicting the behavior of the mechanism with respect to the conical surface. Moreover, we observe that the conical developable mechanisms specified in this paper have motion paths that necessarily contain bifurcation points which lead to an unbounded array of motion paths in the parameterization plane. 
    more » « less
  2. ; (, Peer review)
    Faculty of color are underrepresented in science, technology, engineering, and mathematics (STEM) fields, and this underrepresentation is more evident in the higher ranks of the professoriate. This paper presents the rationale for developing the Pathways for Advancement and Tenure at HBCUs (PATHs) program which, with support from the NSF Alliances for Graduate Education and the Professoriate (AGEP) program, seeks to provide underrepresented faculty at HBCUs with the tools to attain promotion and tenure. PATHs three interventions (grantsmanship, research publications, and quality of life) provide its participating Faculty (PATHs Fellows) with the tools to develop a competitive promotion and tenure application. The expectations and limitations to implementation of the program are discussed in the framework of the current status of HBCUs. 
    more » « less
  3. ; (, Peer review)
    Faculty of color are underrepresented in science, technology, engineering, and mathematics (STEM) fields, and this underrepresentation is more evident in the higher ranks of the professoriate. This paper presents the rationale for developing the Pathways for Advancement and Tenure at HBCUs (PATHs) program which, with support from the NSF Alliances for Graduate Education and the Professoriate (AGEP) program, seeks to provide underrepresented faculty at HBCUs with the tools to attain promotion and tenure. PATHs three interventions (grantsmanship, research publications, and quality of life) provide its participating Faculty (PATHs Fellows) with the tools to develop a competitive promotion and tenure application. The expectations and limitations to implementation of the program are discussed in the framework of the current status of HBCUs. 
    more » « less
  4. ; ; ; ; (, Proceedings of the VLDB Endowment)
    In 2011, we proposed PathSim to systematically define and compute similarity between nodes in a heterogeneous information network (HIN), where nodes and links are from different types. In the PathSim paper, we for the first time introduced HIN with general network schema and proposed the concept of meta-paths to systematically define new relation types between nodes. In this paper, we summarize the impact of PathSim paper in both academia and industry. We start from the algorithms that are based on meta-path-based feature engineering, then move on to the recent development in heterogeneous network representation learning, including both shallow network embedding and heterogeneous graph neural networks. In the end, we make the connection between knowledge graphs and HINs and discuss the implication of meta-paths in the symbolic reasoning scenario. Finally, we point out several future directions. 
    more » « less
  5. (, Mathematics of operations research)
    The Micali–Vazirani (MV) algorithm for finding a maximum cardinality matching in general graphs, which was published in 1980, remains to this day the most efficient known algorithm for the problem. The current paper gives the first complete and correct proof of this algorithm. The MV algorithm resorts to finding minimum-length augmenting paths. However, such paths fail to satisfy an elementary property, called breadth first search honesty in this paper. In the absence of this property, an exponential time algorithm appears to be called for—just for finding one such path. On the other hand, the MV algorithm accomplishes this and additional tasks in linear time. The saving grace is the various “footholds” offered by the underlying structure, which the algorithm uses in order to perform its key tasks efficiently. The theory expounded in this paper elucidates this rich structure and yields a proof of correctness of the algorithm. It may also be of independent interest as a set of well-knit graph-theoretic facts. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email