On the limit value of compactness of some graph classes

Lokot T, Mehler A, Abramov O (2018)
PLOS ONE 13(11): e0207536.

Download
OA 609.60 KB
Zeitschriftenaufsatz | Englisch
Volltext vorhanden für diesen Nachweis
Autor
; ;
Abstract / Bemerkung
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 [1] 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 C_B = 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.
Erscheinungsjahr
Zeitschriftentitel
PLOS ONE
Band
13
Ausgabe
11
Art.-Nr.
e0207536
eISSN
Finanzierungs-Informationen
Article Processing Charge funded by the Deutsche Forschungsgemeinschaft and the Open Access Publication Fund of Bielefeld University.
PUB-ID

Zitieren

Lokot T, Mehler A, Abramov O. On the limit value of compactness of some graph classes. PLOS ONE. 2018;13(11): e0207536.
Lokot, T., Mehler, A., & Abramov, O. (2018). On the limit value of compactness of some graph classes. PLOS ONE, 13(11), e0207536. doi:10.1371/journal.pone.0207536
Lokot, T., Mehler, A., and Abramov, O. (2018). On the limit value of compactness of some graph classes. PLOS ONE 13:e0207536.
Lokot, T., Mehler, A., & Abramov, O., 2018. On the limit value of compactness of some graph classes. PLOS ONE, 13(11): e0207536.
T. Lokot, A. Mehler, and O. Abramov, “On the limit value of compactness of some graph classes”, PLOS ONE, vol. 13, 2018, : e0207536.
Lokot, T., Mehler, A., Abramov, O.: On the limit value of compactness of some graph classes. PLOS ONE. 13, : e0207536 (2018).
Lokot, Tatiana, Mehler, Alexander, and Abramov, Olga. “On the limit value of compactness of some graph classes”. PLOS ONE 13.11 (2018): e0207536.
Alle Dateien verfügbar unter der/den folgenden Lizenz(en):
Creative Commons Namensnennung 4.0 International Public License (CC-BY 4.0):
Volltext(e)
Access Level
OA Open Access
Zuletzt Hochgeladen
2018-12-20T08:15:01Z

Link(s) zu Volltext(en)
Access Level
Restricted Closed Access

9 References

Daten bereitgestellt von Europe PubMed Central.

Structural Similarities of Complex Networks: A Computational Model by Example of Wiki Graphs
AUTHOR UNKNOWN, 2008
Structural Analysis of Hypertexts: Identifying Hierarchies and Useful Metrics
AUTHOR UNKNOWN, 1992

AUTHOR UNKNOWN, 2001
A measure for the cohesion of weighted networks
AUTHOR UNKNOWN, 2003

AUTHOR UNKNOWN, 1995

AUTHOR UNKNOWN, 1996
Automatic Language Classification by Means of Syntactic Dependency Networks
AUTHOR UNKNOWN, 2011

AUTHOR UNKNOWN, 0
The structure and function of complex networks
AUTHOR UNKNOWN, 2003

Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Web of Science

Dieser Datensatz im Web of Science®

Quellen

PMID: 30458027
PubMed | Europe PMC

Suchen in

Google Scholar