On the limit value of compactness of some graph classes

PLoS One. 2018 Nov 20;13(11):e0207536. doi: 10.1371/journal.pone.0207536. eCollection 2018.

Abstract

In this paper, we study the limit of compactness which is a graph index originally introduced for measuring structural characteristics of hypermedia. Applying compactness to large scale small-world graphs (Mehler, 2008) observed its limit behaviour to be equal 1. The striking question concerning this finding was whether this limit behaviour resulted from the specifics of small-world graphs or was simply an artefact. In this paper, we determine the necessary and sufficient conditions for any sequence of connected graphs resulting in a limit value of CB = 1 which can be generalized with some consideration for the case of disconnected graph classes (Theorem 3). This result can be applied to many well-known classes of connected graphs. Here, we illustrate it by considering four examples. In fact, our proof-theoretical approach allows for quickly obtaining the limit value of compactness for many graph classes sparing computational costs.

Publication types

  • Research Support, Non-U.S. Gov't

MeSH terms

  • Data Mining / trends*
  • Hypermedia / trends*
  • Models, Theoretical*

Grants and funding

This work was supported by BMBF (https://www.bmbf.de/) funded project "Linguistic Networks" (http://www.linguistic-networks.net/) and DFG (http://www.dfg.de/) funded project "EcoGest" (https://scs.techfak.uni-bielefeld.de/ecogest/). The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.