Edge importance in a network via line graphs and the matrix exponential | Numerical Algorithms Skip to main content
Springer Nature Link
Log in

Edge importance in a network via line graphs and the matrix exponential

  • Original Paper
  • Published:
Numerical Algorithms Aims and scope Submit manuscript

Abstract

This paper is concerned with the identification of important edges in a network, in both their roles as transmitters and receivers of information. We propose a method based on computing the matrix exponential of a matrix associated with a line graph of the given network. Both undirected and directed networks are considered. Edges may be given positive weights. Computed examples illustrate the performance of the proposed method.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14

Similar content being viewed by others

References

  1. Arrigo, F., Benzi, M.: Edge modification criteria for enhancing the communicability of digraphs. SIAM J. Matrix Anal. Appl. 37, 443–468 (2016)

    Article  MathSciNet  Google Scholar 

  2. Arrigo, F., Benzi, M.: Updating and downdating techniques for optimizing network communicability. SIAM J. Sci. Comput. 38, B25–B49 (2016)

    Article  MathSciNet  Google Scholar 

  3. Benzi, M., Estrada, E., Klymko, C.: Ranking hubs and authorities using matrix functions. Linear Algebra Appl. 438, 2447–2474 (2013)

    Article  MathSciNet  Google Scholar 

  4. Benzi, M., Klymko, C.: Total communicability as a centrality measure. J. Complex Networks 1, 124–149 (2013)

    Article  Google Scholar 

  5. Chen, C., Jia, Z., Varaiya, P.: Causes and cures of highway congestion. IEEE Control. Syst. Mag. 21, 26–32 (2001)

    Article  Google Scholar 

  6. Chen, W.-K.: Graph Theory and Its Engineering Applications. World Scientific, Singapore (1997)

    Book  Google Scholar 

  7. De la Cruz Cabrera, O., Matar, M., Reichel, L.: Analysis of directed networks via the matrix exponential. J. Comput. Appl Math. 355, 182–192 (2019)

    Article  MathSciNet  Google Scholar 

  8. Diestel, R.: Graph Theory. Springer, Berlin (2000)

    MATH  Google Scholar 

  9. Estrada, E.: Edge adjacency relationships and a novel topological index related to molecular volume. J. Chem. Inf. Comput. Sci. 35, 31–33 (1995)

    Article  Google Scholar 

  10. Estrada, E.: The Structure of Complex Networks: Theory and Applications. Oxford University Press, Oxford (2012)

    MATH  Google Scholar 

  11. Estrada, E., Hatano, N.: Statistical-mechanical approach to subgraph centrality in complex networks. Chem. Phys. Lett. 439, 247–251 (2007)

    Article  Google Scholar 

  12. Estrada, E., Higham, D.J.: Network properties revealed through matrix functions. SIAM Rev. 52, 696–714 (2010)

    Article  MathSciNet  Google Scholar 

  13. Federal Aviation Administration (FAA). Passenger boarding (enplanement) and all-cargo data for US airports, 2016

  14. Fenu, C., Martin, D., Reichel, L., Rodriguez, G.: Network analysis via partial spectral factorization and Gauss quadrature. SIAM J. Sci. Comput. 35, A2046–A2068 (2013)

    Article  MathSciNet  Google Scholar 

  15. Godsil, C., Royle, G.F.: Algebraic Graph Theory. Springer, New York (2013)

    MATH  Google Scholar 

  16. Golub, G.H., Van Loan, C.F.: Matrix Computations. John Hopkins University Press, Baltimore (2013)

    MATH  Google Scholar 

  17. Gross, J.L., Yellen, J.: Graph Theory and Its Applications, 2nd edn. Taylor & Francis, Boca Raton (2006)

  18. Gutman, I., Estrada, E.: Topological indices based on the line graph of the molecular graph. J. Chem. Inf. Comput. Sci. 36, 541–543 (1996)

    Article  Google Scholar 

  19. Katz, L.: A new status index derived from sociometric analysis. Psychometrika 18, 39–43 (1953)

    Article  Google Scholar 

  20. Kleinberg, J.M.: Authoritative sources in a hyperlinked environment. J. ACM 46, 604–632 (1999)

    Article  MathSciNet  Google Scholar 

  21. Newman, M.E.J.: Networks: An Introduction. Oxford University Press, Oxford (2010)

    Book  Google Scholar 

  22. Bureau of Transportation Statistics. Research and Innovative Technology Administration/Transtats

  23. Orlin, J.: Contentment in graph theory: covering graphs with cliques. Indagationes Mathematicae (Proceedings) 80, 406–424 (1977)

    Article  MathSciNet  Google Scholar 

  24. Thulasiraman, K., Swamy, M.N.S.: Graphs: Theory and Algorithms. Wiley, New York (1992)

    Book  Google Scholar 

Download references

Funding

This research is financially supported in part by NSF grants DMS-1720259 and DMS-1729509.

Author information

Authors and Affiliations

  1. Department of Mathematical Sciences, Kent State University, Kent, OH, 44242, USA

    Omar De la Cruz Cabrera, Mona Matar & Lothar Reichel

Authors
  1. Omar De la Cruz Cabrera
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Mona Matar
    View author publications

    You can also search for this author inPubMed Google Scholar

  3. Lothar Reichel
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to Omar De la Cruz Cabrera.

Additional information

Publisher’s note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

De la Cruz Cabrera, O., Matar, M. & Reichel, L. Edge importance in a network via line graphs and the matrix exponential. Numer Algor 83, 807–832 (2020). https://doi.org/10.1007/s11075-019-00704-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11075-019-00704-y

Keywords