Accessibility and delay in random temporal networks
In a wide range of complex networks, the links between the nodes are temporal and may sporadically appear and disappear. This temporality is fundamental to analyzing the formation of paths within such networks. Moreover, the presence of the links between the nodes is a random process induced by natu...
| Príomhchruthaitheoirí: | , , |
|---|---|
| Formáid: | Journal article |
| Foilsithe / Cruthaithe: |
American Physical Society
2017
|
| _version_ | 1826273904998481920 |
|---|---|
| author | Tajbakhsh, S Coon, JP Simmons, DE |
| author_facet | Tajbakhsh, S Coon, JP Simmons, DE |
| author_sort | Tajbakhsh, S |
| collection | OXFORD |
| description | In a wide range of complex networks, the links between the nodes are temporal and may sporadically appear and disappear. This temporality is fundamental to analyzing the formation of paths within such networks. Moreover, the presence of the links between the nodes is a random process induced by nature in many real-world networks. In this paper, we study random temporal networks at a microscopic level and formulate the probability of accessibility from a node i to a node j after a certain number of discrete time units T . While solving the original problem is computationally intractable, we provide an upper and two lower bounds on this probability for a very general case with arbitrary time-varying probabilities of the links' existence. Moreover, for a special case where the links have identical probabilities across the network at each time slot, we obtain the exact probability of accessibility between any two nodes. Finally, we discuss scenarios where the information regarding the presence and absence of links is initially available in the form of time duration (of presence or absence intervals) continuous probability distributions rather than discrete probabilities over time slots. We provide a method for transforming such distributions to discrete probabilities, which enables us to apply the given bounds in this paper to a broader range of problem settings. |
| first_indexed | 2024-03-06T22:35:20Z |
| format | Journal article |
| id | oxford-uuid:59b1f602-884b-44df-b9f0-74124a82ad49 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T22:35:20Z |
| publishDate | 2017 |
| publisher | American Physical Society |
| record_format | dspace |
| spelling | oxford-uuid:59b1f602-884b-44df-b9f0-74124a82ad492022-03-26T17:11:14ZAccessibility and delay in random temporal networksJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:59b1f602-884b-44df-b9f0-74124a82ad49Symplectic Elements at OxfordAmerican Physical Society2017Tajbakhsh, SCoon, JPSimmons, DEIn a wide range of complex networks, the links between the nodes are temporal and may sporadically appear and disappear. This temporality is fundamental to analyzing the formation of paths within such networks. Moreover, the presence of the links between the nodes is a random process induced by nature in many real-world networks. In this paper, we study random temporal networks at a microscopic level and formulate the probability of accessibility from a node i to a node j after a certain number of discrete time units T . While solving the original problem is computationally intractable, we provide an upper and two lower bounds on this probability for a very general case with arbitrary time-varying probabilities of the links' existence. Moreover, for a special case where the links have identical probabilities across the network at each time slot, we obtain the exact probability of accessibility between any two nodes. Finally, we discuss scenarios where the information regarding the presence and absence of links is initially available in the form of time duration (of presence or absence intervals) continuous probability distributions rather than discrete probabilities over time slots. We provide a method for transforming such distributions to discrete probabilities, which enables us to apply the given bounds in this paper to a broader range of problem settings. |
| spellingShingle | Tajbakhsh, S Coon, JP Simmons, DE Accessibility and delay in random temporal networks |
| title | Accessibility and delay in random temporal networks |
| title_full | Accessibility and delay in random temporal networks |
| title_fullStr | Accessibility and delay in random temporal networks |
| title_full_unstemmed | Accessibility and delay in random temporal networks |
| title_short | Accessibility and delay in random temporal networks |
| title_sort | accessibility and delay in random temporal networks |
| work_keys_str_mv | AT tajbakhshs accessibilityanddelayinrandomtemporalnetworks AT coonjp accessibilityanddelayinrandomtemporalnetworks AT simmonsde accessibilityanddelayinrandomtemporalnetworks |