Abstract
We introduce a new method to characterize the network reliability polynomial of graphs – and hence the graph itself – using only a few parameters. Exact evaluation of the reliability polynomial is almost impossible for large graphs; estimating the polynomial’s coefficients is feasible but requires significant computation. Furthermore, the information required to specify the polynomial scales with the size of the graph. Thus, we aim to develop a way to characterize the polynomial well with as few parameters as possible. We show that the error function provides a two-parameter family of functions that can closely reproduce reliability polynomials of both random graphs and synthetic social networks. These parameter values can be used as statistics for characterizing the structure of entire networks in ways that are sensitive to dynamical properties of interest.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Moore, E., Shannon, C.: Reliable circuits using less reliable relays. Journal of the Franklin Institute 262, 191–208 (1956)
Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network flows: theory, algorithms, and applications. Prentice Hall (1993)
Ford, L.R., Fulkerson, D.R.: Flows in Networks. Princeton University Press (1962)
Colbourn, C.J.: The Combinatorics of Network Reliability. Oxford University Press (1987)
Eubank, S., Youssef, M., Khorramzadeh, Y.: Determining and understanding dynamically important differences between complex networks using reliability-induced structural motifs. In: 2013 International Conference on Signal-Image Technology & Internet-Based Systems (SITIS), Complex Networks Workshop, Tokyo, Japan, December 2-5 (2013)
Eubank, S., Youssef, M., Khorramzadeh, Y.: Using the network reliability polynomial to characterize and design networks. Journal of Complex Networks, 1–17 (2014)
Halloran, M., Vespignani, A., Bharti, N., Feldstein, L., Alexander, K., Ferrari, M., Shaman, J., Drake, J., Porco, T., Eisenberg, J., Valle, S., Lofgren, E., Scarpino, S., Eisenberg, M., Gao, D., Hyman, J., Eubank, S.: Ebola: Mobility data. Science 346 (2014)
Youssef, M., Khorramzadeh, Y., Eubank, S.: Network reliability: the effect of local network structure on diffusive processes. Physical Review E 66 (2013)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Nath, M., Eubank, S., Youssef, M., Khorramzadeh, Y., Mowlaei, S. (2015). A Two-Parameter Method to Characterize the Network Reliability for Diffusive Processes. In: Mangioni, G., Simini, F., Uzzo, S., Wang, D. (eds) Complex Networks VI. Studies in Computational Intelligence, vol 597. Springer, Cham. https://doi.org/10.1007/978-3-319-16112-9_14
Download citation
DOI: https://doi.org/10.1007/978-3-319-16112-9_14
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-16111-2
Online ISBN: 978-3-319-16112-9
eBook Packages: EngineeringEngineering (R0)