Summary

Proceedings of the 2013 International Symposium on Nonlinear Theory and its Applications

2013

Session Number:A4L-A

Session:

Number:130

On Graphs that Locally Maximize Global Clustering Coefficient

Tetsuro Teraji,  Norikazu Takahashi,  

pp.130-133

Publication Date:

Online ISSN:2188-5079

DOI:10.15248/proc.2.130

PDF download (277.3KB)

The problem of finding graphs that locally maximize the global clustering coefficient (GCC) is considered. We first prove that if a graph is composed of two cliques sharing one vertex then it locally maximizes the GCC. We next prove that if a graph is composed of two cliques connected by a path with an arbitrary length then it locally maximizes the GCC. The first result is the same as the one given in the case of the average clustering coefficient (ACC). On the other hand, the second one does not hold in the case of the ACC.

[1] D. J. Watts and S. H. Strogatz, “Collective dynamics of ‘small-world' networks,” Nature, vol.393, pp.440-442, 1998.

[2] M. E. Newman, S. H. Strogatz and D. J. Watts, “Random graphs with arbitrary degree distributions and their applications,” Physical Review E, vol.64, 026118, 2001.

[3] B. J. Kim, “Performance of networks of artificial neurons: The role of clustering,” Physical Review E, vol.69, 045101, 2004.

[4] P. N. McGraw and M. Menzinger, “Clustering and the synchronization of oscillator networks,” Physical Review E, vol.72, 015101, 2005.

[5] S. Koizuka and N. Takahashi, “Maximum clustering coefficient of graphs with given number of vertices and edges,” Nonlinear Theory and Its Applications, IEICE, vol.2, no.4, pp.443-457, 2011.

[6] T. Fukami and N. Takahashi, “New classes of clustering coefficient locally maximizing graphs,” submitted.