×

Spectral bounds for the betweenness of a graph. (English) Zbl 1114.05058

Summary: 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.).

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C12 Distance in graphs
05C38 Paths and cycles
15A18 Eigenvalues, singular values, and eigenvectors
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chung, F. R.K.; Coman, E. G.; Reiman, M. I.; Simon, B. E., The forwarding index of communication networks, IEEE Trans. Inform. Theory, 33, 224-232 (1987) · Zbl 0626.94019
[2] Fiedler, M., Algebraic connectivity of graphs, Czechoslovak Math. J., 23, 298-305 (1973) · Zbl 0265.05119
[3] S. Gago, Métodos espectrales y nuevas medidas modelos y parámetros en grafos pequeño-mundo invariantes de escala, Ph.D. Thesis Universitat Politécnica de Catalunya, 2006, (in Spanish).; S. Gago, Métodos espectrales y nuevas medidas modelos y parámetros en grafos pequeño-mundo invariantes de escala, Ph.D. Thesis Universitat Politécnica de Catalunya, 2006, (in Spanish).
[4] Freeman, L. C., A set of measures of centrality based upon betweenness, Sociometry, 40, 35-41 (1977)
[5] Girvan, M.; Newman, M. E.J., Community structure in social and biological networks, Proc. Natl. Acad. Sci. USA, 99, 7821-7826 (2002) · Zbl 1032.91716
[6] Goh, K.-I.; OH, E.; Jeong, H.; Kahng, B.; Kim, D., Classification of scale-free networks, Proc. Natl. Acad. Sci. USA, 99, 12583-12588 (2002) · Zbl 1063.82017
[7] Heydemann, M. C.; Meyer, J. C.; Sotteau, D., On forwarding indices of networks, Discrete Appl. Math., 23, 103-123 (1987) · Zbl 0681.90077
[8] Mohar, B., Isoperimetric numbers of graphs, J. Combin. Theory Ser. B, 47, 274-291 (1989) · Zbl 0719.05042
[9] Newman, M. E.J., The structure and function of complex networks, SIAM Rev., 45, 167-256 (2003) · Zbl 1029.68010
[10] Newman, M. E.J.; Girvan, M., Finding and evaluating community structure in networks, Phys. Rev. E, 69, 026113 (2004)
[11] Solé, P., Expanding and forwarding, Discrete Appl. Math., 58, 67-78 (1995) · Zbl 0820.05034
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.