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

详细信息    查看全文

• 作者：Tatsuya Fukami^a ; Norikazu Takahashi^b ; ^{takahashi@cs.okayama-u.ac.jp}
• 关键词：Clustering coefficient ; Complex network ; 2-switch
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：30 January 2017
• 年：2017
• 卷：217
• 期：part_P3
• 页码：525-535
• 全文大小：494 K
• 卷排序：217

文摘

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.