Large values of the clustering coefficient |
| |
Authors: | Michael Gentner Irene Heinrich Simon Jäger Dieter Rautenbach |
| |
Institution: | 1. Institute of Optimization and Operations Research, Ulm University, Ulm, Germany;2. Department of Mathematics, University of Kaiserslautern, Kaiserslautern, Germany |
| |
Abstract: | A prominent parameter in the context of network analysis, originally proposed by Watts and Strogatz (1998), is the clustering coefficient of a graph . It is defined as the arithmetic mean of the clustering coefficients of its vertices, where the clustering coefficient of a vertex of is the relative density of its neighborhood if is at least , and otherwise. It is unknown which graphs maximize the clustering coefficient among all connected graphs of given order and size.We determine the maximum clustering coefficients among all connected regular graphs of a given order, as well as among all connected subcubic graphs of a given order. In both cases, we characterize all extremal graphs. Furthermore, we determine the maximum increase of the clustering coefficient caused by adding a single edge. |
| |
Keywords: | Clustering coefficient Connected caveman graph Cliquishness |
本文献已被 ScienceDirect 等数据库收录! |
|