TY - JOUR

T1 - Graphs that locally maximize clustering coefficient in the space of graphs with a fixed degree sequence

AU - Fukami, Tatsuya

AU - Takahashi, Norikazu

N1 - Publisher Copyright:
© 2016 Elsevier B.V.

PY - 2017/1/30

Y1 - 2017/1/30

N2 - This paper studies the problem of finding graphs that locally maximize the clustering coefficient in the space of graphs with a fixed degree sequence. Such a graph is characterized by the property that the clustering coefficient cannot be increased, no matter how a single 2-switch is applied. First, an explicit formula for the amount of change in the clustering coefficient of a graph caused by a single 2-switch is given. Next, some classes of graphs with the property stated above are presented. An example of such a graph is the one obtained from a tree by replacing its edges with cliques with the same order.

AB - This paper studies the problem of finding graphs that locally maximize the clustering coefficient in the space of graphs with a fixed degree sequence. Such a graph is characterized by the property that the clustering coefficient cannot be increased, no matter how a single 2-switch is applied. First, an explicit formula for the amount of change in the clustering coefficient of a graph caused by a single 2-switch is given. Next, some classes of graphs with the property stated above are presented. An example of such a graph is the one obtained from a tree by replacing its edges with cliques with the same order.

KW - 2-switch

KW - Clustering coefficient

KW - Complex network

UR - http://www.scopus.com/inward/record.url?scp=85001784669&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85001784669&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2016.10.002

DO - 10.1016/j.dam.2016.10.002

M3 - Article

AN - SCOPUS:85001784669

SN - 0166-218X

VL - 217

SP - 525

EP - 535

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -