Spectral bounds for the betweenness of a graph

被引：26

作者：

Comellas, F. ^{[1
]}

Gago, S. ^{[1
]}

机构：

[1] Univ Politecn Cataluna, Dept Matemat Aplicada 4, E-08680 Castelldefels, Spain

来源：

LINEAR ALGEBRA AND ITS APPLICATIONS | 2007年 / 423卷 / 01期

关键词：

graphs; Laplacian matrix; spectra; eigenvalues; betweenness; edge-betweenness; isoperimetric number;

D O I：

10.1016/j.laa.2006.08.027

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In this paper we find spectral bounds (Laplacian matrix) for the vertex and the edge betweenness of a graph. We also relate the edge betweenness with the isoperimetric number and the edge forwarding and edge expansion indices of the graph allowing a new upper bound on its diameter. The results are of interest as they can be used in the study of communication properties of real networks, in particular for dynamical processes taking place on them (broadcasting, network synchronization, virus spreading, etc.). (C) 2006 Elsevier Inc. All rights reserved.

引用

页码：74 / 80

页数：7

共 11 条

[1] FORWARDING INDEX OF COMMUNICATION NETWORKS. [J].

Chung, Fan R.K. ;

Coffman Jr., Edward G. ;

Reiman, Martin I. ;

Simon, Burton .

IEEE Transactions on Information Theory, 1987, IT-33 (02) :224-232

[2]

FIEDLER M, 1973, CZECH MATH J, V23, P298

[3] SET OF MEASURES OF CENTRALITY BASED ON BETWEENNESS [J].

FREEMAN, LC .

SOCIOMETRY, 1977, 40 (01) :35-41

[4]

Gago S., 2006, THESIS U POLITECNICA

[5] Community structure in social and biological networks [J].

Girvan, M ;

Newman, MEJ .

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2002, 99 (12) :7821-7826

[6] Classification of scale-free networks [J].

Goh, KI ;

Oh, E ;

Jeong, H ;

Kahng, B ;

Kim, D .

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2002, 99 (20) :12583-12588

[7] ON FORWARDING INDEXES OF NETWORKS [J].

HEYDEMANN, MC ;

MEYER, JC ;

SOTTEAU, D .

DISCRETE APPLIED MATHEMATICS, 1989, 23 (02) :103-123

[8] ISOPERIMETRIC NUMBERS OF GRAPHS [J].

MOHAR, B .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1989, 47 (03) :274-291

[9] The structure and function of complex networks [J].

Newman, MEJ .

SIAM REVIEW, 2003, 45 (02) :167-256

[10] Finding and evaluating community structure in networks [J].

Newman, MEJ ;

Girvan, M .

PHYSICAL REVIEW E, 2004, 69 (02) :026113-1

← 1 2 →