{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,17]],"date-time":"2026-02-17T05:42:02Z","timestamp":1771306922893,"version":"3.50.1"},"reference-count":36,"publisher":"MDPI AG","issue":"7","license":[{"start":{"date-parts":[[2022,6,29]],"date-time":"2022-06-29T00:00:00Z","timestamp":1656460800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CPS 2128378"],"award-info":[{"award-number":["CPS 2128378"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS 2107014"],"award-info":[{"award-number":["CNS 2107014"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS 2150152"],"award-info":[{"award-number":["CNS 2150152"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS 1824440"],"award-info":[{"award-number":["CNS 1824440"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS 1828363"],"award-info":[{"award-number":["CNS 1828363"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS 1757533"],"award-info":[{"award-number":["CNS 1757533"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Effective non-repetitive routing among nodes in a network is an essential function in communication networks. To achieve that, pruning the links of the network is helpful with the trade-off of making the network less robust in transmitting messages while reducing redundancy to increase flow with limited network bandwidth, so we enhance the quality of service (QoS). In our paper, we study the case that if a link removal has either no effect or an insignificant effect on the Age of Information (AoI) of the messages delivered in the communication network. The pruning of such links can be applied to the k least significant links in terms of their impact on the AoI of the messages transmitted in the system. The objective of our work is to study the effect of pruning a number of links in a network on the AoI, in order to reduce the redundancy of the messages that may be received at the destination many times while transmitted only once. In our context, the objective of the communication system would be to maintain the information from the source as fresh as possible when it arrives at the destination while reducing the redundancy of messages. In this work, we introduce an efficient reduction method designed for series-parallel networks with links of exponentially distributed wait times. In addition, we consider the deterministic case and present the pruning technique when link removal would not affect the AoI. Lastly, we present a comprehensive simulation to study the effect of pruning the links on the AoI of the network and the redundancy of messages received by the destination.<\/jats:p>","DOI":"10.3390\/a15070228","type":"journal-article","created":{"date-parts":[[2022,6,29]],"date-time":"2022-06-29T20:47:56Z","timestamp":1656535676000},"page":"228","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On Edge Pruning of Communication Networks under an Age-of-Information Framework"],"prefix":"10.3390","volume":"15","author":[{"given":"Abdalaziz","family":"Sawwan","sequence":"first","affiliation":[{"name":"Department of Computer and Information Sciences, Temple University, Philadelphia, PA 19122, USA"}]},{"given":"Jie","family":"Wu","sequence":"additional","affiliation":[{"name":"Department of Computer and Information Sciences, Temple University, Philadelphia, PA 19122, USA"}]}],"member":"1968","published-online":{"date-parts":[[2022,6,29]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1038\/nphys2257","article-title":"The organization of strong links in complex networks","volume":"8","author":"Pajevic","year":"2012","journal-title":"Nat. Phys."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"198701","DOI":"10.1103\/PhysRevLett.87.198701","article-title":"Efficient behavior of small-world networks","volume":"87","author":"Latora","year":"2001","journal-title":"Phys. Rev. Lett."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1038\/35019019","article-title":"Error and attack tolerance of complex networks","volume":"406","author":"Albert","year":"2000","journal-title":"Nature"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1016\/j.physa.2014.06.079","article-title":"Efficiency of attack strategies on complex model and real-world networks","volume":"414","author":"Bellingeri","year":"2014","journal-title":"Phys. Stat. Mech. Its Appl."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"13513","DOI":"10.1038\/s41598-018-31902-8","article-title":"A comparative analysis of approaches to network-dismantling","volume":"8","author":"Wandelt","year":"2018","journal-title":"Sci. Rep."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Iyer, S., Killingback, T., Sundaram, B., and Wang, Z. (2013). Attack robustness and centrality of complex networks. PLoS ONE, 8.","DOI":"10.1371\/journal.pone.0059613"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1007\/s12080-012-0166-0","article-title":"Threshold extinction in food webs","volume":"6","author":"Bellingeri","year":"2013","journal-title":"Theor. Ecol."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"13922","DOI":"10.1038\/s41598-018-32020-1","article-title":"Structural robustness of mammalian transcription factor networks reveals plasticity across development","volume":"8","year":"2018","journal-title":"Sci. Rep."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ecolmodel.2012.12.011","article-title":"Increasing the extinction risk of highly connected species causes a sharp robust-to-fragile transition in empirical food webs","volume":"251","author":"Bellingeri","year":"2013","journal-title":"Ecol. Model."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1140\/epjst\/e2013-01711-9","article-title":"Modelling the air transport with complex networks: A short review","volume":"215","author":"Zanin","year":"2013","journal-title":"Eur. Phys. J. Spec. Top."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"188701","DOI":"10.1103\/PhysRevLett.94.188701","article-title":"Stability and topology of scale-free networks under attack and defense strategies","volume":"94","author":"Gallos","year":"2005","journal-title":"Phys. Rev. Lett."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"058701","DOI":"10.1103\/PhysRevLett.101.058701","article-title":"Finding a better immunization strategy","volume":"101","author":"Chen","year":"2008","journal-title":"Phys. Rev. Lett."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1016\/j.physa.2018.06.127","article-title":"Efficacy of local attack strategies on the Beijing road complex weighted network","volume":"510","author":"Bellingeri","year":"2018","journal-title":"Phys. Stat. Mech. Its Appl."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"8567","DOI":"10.1038\/s41598-017-08714-3","article-title":"Network robustness assessed within a dual connectivity framework: Joint dynamics of the Active and Idle Networks","volume":"7","author":"Tejedor","year":"2017","journal-title":"Sci. Rep."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"1807","DOI":"10.1109\/TIT.2018.2871079","article-title":"The age of information: Real-time status updating by multiple sources","volume":"65","author":"Yates","year":"2018","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"854","DOI":"10.1109\/JSAC.2020.2980911","article-title":"Minimizing age of information with power constraints: Multi-user opportunistic scheduling in multi-state time-varying channels","volume":"38","author":"Tang","year":"2020","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1183","DOI":"10.1109\/JSAC.2021.3065072","article-title":"Age of information: An introduction and survey","volume":"39","author":"Yates","year":"2021","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Costa, M., Codreanu, M., and Ephremides, A. (July, January 29). Age of information with packet management. Proceedings of the 2014 IEEE International Symposium on Information Theory, Honolulu, HI, USA.","DOI":"10.1109\/ISIT.2014.6875100"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Yates, R.D. (2021). The Age of Gossip in Networks. arXiv.","DOI":"10.1109\/ISIT45174.2021.9517796"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Li, Z., and Shen, H. (2008, January 8\u201312). Utility-based distributed routing in intermittently connected networks. Proceedings of the 2008 37th International Conference on Parallel Processing, Portland, OR, USA.","DOI":"10.1109\/ICPP.2008.77"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Xiao, M., Wu, J., Liu, C., and Huang, L. (2003, January 14\u201319). Tour: Time-sensitive opportunistic utility-based routing in delay tolerant networks. Proceedings of the 2013 Proceedings IEEE Infocom, Turin, Italy.","DOI":"10.1109\/INFCOM.2013.6567010"},{"key":"ref_22","unstructured":"Xue, Y., Cui, Y., and Nahrstedt, K. (2005, January 22\u201324). A utility-based distributed maximum lifetime routing algorithm for wireless networks. Proceedings of the Second International Conference on Quality of Service in Heterogeneous Wired\/Wireless Networks (QSHINE\u201905), Lake Buena Vista, FL, USA."},{"key":"ref_23","unstructured":"Toh, C.K. (1996, January 27\u201329). A novel distributed routing protocol to support ad hoc mobile computing. Proceedings of the 1996 IEEE Fifteenth Annual International Phoenix Conference on Computers and Communications, Scottsdale, AZ, USA."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1109\/INFCOM.2003.1208679","article-title":"A framework for reliable routing in mobile ad hoc networks","volume":"Volume 1","author":"Ye","year":"2003","journal-title":"Proceedings of the IEEE INFOCOM 2003. Twenty-second Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE Cat. No. 03CH37428)"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Zhou, F., Malher, S., and Toivonen, H. (2010, January 13\u201317). Network simplification with minimal loss of connectivity. Proceedings of the 2010 IEEE International Conference on Data Mining, Sydney, Australia.","DOI":"10.1109\/ICDM.2010.133"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Zhou, F., Mahler, S., and Toivonen, H. (2012). Simplification of networks by edge pruning. Bisociative Knowledge Discovery, Springer.","DOI":"10.1007\/978-3-642-31830-6_13"},{"key":"ref_27","unstructured":"Singh, L. (2005, January 27\u201330). Pruning social networks using structural properties and descriptive attributes. Proceedings of the Fifth IEEE International Conference on Data Mining (ICDM\u201905), Houston, TX, USA."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1016\/S0304-3975(97)00124-2","article-title":"A linear time algorithm for computing the most reliable source on a series-parallel graph with unreliable edges","volume":"209","author":"Colbourn","year":"1998","journal-title":"Theor. Comput. Sci."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/0890-5401(92)90041-D","article-title":"Parallel recognition of series-parallel graphs","volume":"98","author":"Eppstein","year":"1992","journal-title":"Inf. Comput."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1561\/1300000060","article-title":"Age of information: A new concept, metric, and tool","volume":"12","author":"Kosta","year":"2017","journal-title":"Found. Trends Netw."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"145","DOI":"10.2143\/AST.35.1.583170","article-title":"A review on phase-type distributions and their use in risk theory","volume":"35","author":"Bladt","year":"2005","journal-title":"ASTIN Bull. J. IAA"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"515","DOI":"10.2307\/1427620","article-title":"Phase-type distributions and invariant polytopes","volume":"23","year":"1991","journal-title":"Adv. Appl. Probab."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"566","DOI":"10.1080\/0020717031000114986","article-title":"Phase-type distributions and representations: Some results and open problems for system theory","volume":"76","author":"Commault","year":"2003","journal-title":"Int. J. Control"},{"key":"ref_34","unstructured":"Kom\u00e1rkov\u00e1, Z. (2012). Phase-Type Approximation Techniques. [Ph.D. Thesis, Masarykova Univerzita, Fakulta Informatiky]."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Papoulis, A., and Saunders, H. (1989). Probability, Random Variables and Stochastic Processes, Tata McGraw-Hill Education.","DOI":"10.1115\/1.3269815"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1088\/0305-4470\/15\/2\/011","article-title":"Products and compositions with the Dirac delta function","volume":"15","author":"Raju","year":"1982","journal-title":"J. Phys. Math. Gen."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/7\/228\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T23:40:12Z","timestamp":1760139612000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/7\/228"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,29]]},"references-count":36,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2022,7]]}},"alternative-id":["a15070228"],"URL":"https:\/\/doi.org\/10.3390\/a15070228","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,6,29]]}}}