EXTENDED CLUSTERING COEFFICIENTS:GENERALIZATION OF CLUSTERING COEFFICIENTS IN SMALL-WORLD NETWORKS |
| |
作者单位: | [1]Department of Computer Science, South China University of Technology, Guangzhou 510641, China [2]Department of Electrical & ComputerEngineering, University of California, Santa Barbara, CA 93106-9560, USA |
| |
摘 要: | The clustering coefficient C of a network, which is a measure of direct connectivity between neighbors of the various nodes, ranges from 0 (for no connectivity) to 1 (for full connectivity). We define extended clustering coefficients C(h) of a small-world network based on nodes that are at distance h from a source node, thus generalizing distance-1 neighborhoods employed in computing the ordinary clustering coefficient C = C(1). Based on known results about the distance distribution Pδ(h) in a network, that is, the probability that a randomly chosen pair of vertices have distance h, we derive and experimentally validate the law Pδ(h)C(h) ≤ c log N / N, where c is a small constant that seldom exceeds 1. This result is significant because it shows that the product Pδ(h)C(h) is upper-bounded by a value that is considerably smaller than the product of maximum values for Pδ(h) and C(h). Extended clustering coefficients and laws that govern them offer new insights into the structure of small-world networks and open up avenues for further exploration of their properties.
|
关 键 词: | 聚类系数 距离分布 扩展范围 工程数学 |
Extended clustering coefficients:Generalization of clustering coefficients in small-world networks |
| |
Authors: | Wenjun Xiao Wenhong Wei Weidong Chen Yong Qin Behrooz Parhami |
| |
Institution: | 1. Department of Computer Science, South China University of Technology,Guangzhou 510641, China 2. Department of Electrical & Computer Engineering, University of California,Santa Barbara, CA 93106-9560, USA |
| |
Abstract: | The clustering coefficient C of a network, which is a measure of direct connectivity between neighbors of the various nodes, ranges from 0 (for no connectivity)
to 1 (for full connectivity). We define extended clustering coefficients C(h) of a small-world network based on nodes that are at distance h from a source node, thus generalizing distance-1 neighborhoods employed in computing the ordinary clustering coefficient
C = C(1). Based on known results about the distance distribution P
δ
(h) in a network, that is, the probability that a randomly chosen pair of vertices have distance h, we derive and experimentally validate the law P
δ
(h)C(h) ≤ c log N / N, where c is a small constant that seldom exceeds 1. This result is significant because it shows that the product P
δ
(h)C(h) is upper-bounded by a value that is considerably smaller than the product of maximum values for P
δ
(h) and C(h). Extended clustering coefficients and laws that govern them offer new insights into the structure of small-world networks
and open up avenues for further exploration of their properties.
This work was supported in part by the Natural Science Foundation of Guangdong Province under Grant No. 04020130. The original
version was presented on the International Conference on Computational Science (ICCS 2007)
Wenjun Xiao received the Ph.D degree in mathematics from Sichuan University, People’s Republic of China, in 1989. Currently, he is a
professor in the School of Computer Science and Engineering, South China University of Technology, Guangzhou, People’s Republic
of China. His research interests include discrete mathematics, parallel and distributed computing, complex networks, and software
architecture. He has published more than 50 papers in journals and conferences on these topics since 1985.
Wenhong Wei, Weidong Chen and Yong Qin are Ph.D candidates in the School of Computer Science and Engineering, South China University of Technology, Guangzhou, People’s
Republic of China. Their research interests include parallel and distributed computing and networks.
Behrooz Parhami received the Ph.D degree in computer science from the University of California, Los Angeles, in 1973. Presently, he is a
professor in the Department of Electrical and Computer Engineering, University of California, Santa Barbara. His research
deals with parallel architectures and algorithms, computer arithmetic, and reliable computing. In his previous position with
Sharif University of Technology in Tehran, Iran (1974-1988), he was also involved in the areas of educational planning, curriculum
development, standardization efforts, technology transfer, and various editorial responsibilities, including a five-year term
as editor of Computer Report, a Farsilanguage computing periodical. Dr. Parhami’s technical publications include more than
220 papers in journals and international conferences, a Farsi-language textbook, and an English/Farsi glossary of computing
terms. Among his latest publications are two graduate-level textbooks on parallel processing (Plenum, 1999) and computer arithmetic
(Oxford, 2000), and an introductory textbook on computer architecture (Oxford, 2005). Dr. Parhami is a fellow the IEEE and
the IEEE Computer Society, a chartered fellow of the British Computer Society, a member of the ACM, and a distinguished member
of the Informatics Society of Iran, for which he served as a founding member and president from 1979-1984. He also served
as chairman of the IEEE Iran Section (1977-1986) and received the IEEE Centennial Medal in 1984. |
| |
Keywords: | Clustering coefficient small-world extended clustering coefficient distance distribution |
本文献已被 维普 万方数据 SpringerLink 等数据库收录! |
|