This paper introduces a set of component importance measures that are based on theconceptofcriticalﬂow. Inparticular,itshowshowﬂow-basedcentralitymeasures canbeusedtoidentifycriticalcomponentsofaninfrastructuresystem. Themotivation of the work is to provide municipalities with a means of reasoning about the impact of urban interventions. An infrastructure system is represented as a ﬂow network in whichdemandnodesareassignedbothdemandvaluesandcriticalityratings. Sensitive elements in the network are those that carry critical ﬂows, where a ﬂow is deemed critical to the extent that it satisﬁes critical demand. A method for computing these ﬂows is presented, and its utility is demonstrated by comparing the new measures to existing ﬂow centrality measures. The paper also shows how critical ﬂow measures may be combined with standard approaches to reliability analysis. 1 1 Introduction This paper describes a set of component importance measures (“CIMs") that rank system components according to their role in the delivery of resources to critical locations. These measures can be viewed as variants of ﬂow centrality [20] that are customized for ﬂow networks in which demand nodes are assigned both demand values and criticality ratings. ThepaperdescribesageneralmethodforcomputingcriticalﬂowCIMs,aswellasasimple embodiment that demonstrates the various stages of computation. The perspective on infrastructure criticality adopted in this work is demand-based , motivated by an interest in decision support systems (“DSS") [24] for use by municipal governments (see [22, 11]). As urbanization continues at a rapid pace [53, 47] cities are experiencing signiﬁcant increases in population and concomitant increases in demand for goods and services. The resulting capacity issues are a major source of risk for legacy infrastructure systems due to the fact that they are typically extremely expensive to alter (e.g., the Thames Tideway tunnel project [51, 52]). Inadditiontopopulationgrowth,variousinterventionshavethepotentialtoalterpatterns of demand, and therefore to change the distribution of ﬂows within infrastructure systems. For example, densiﬁcation entails the construction of high density residential units that impose heavier demands on legacy infrastructure systems [27]. These changes in demand patternscanalteringexistingﬂowdistributionsandpotentiallychangethesetofcomponents that are relied upon to deliver resources to critical locations. Intheworstcase,changesindemandmayimposeunduestressonexistinginfrastructure. Increasesindemand(orreductionsincapacity)mayleavecriticallocationssuchashospitals with reduced access to resources. Resource ﬂow to critical locations may also be routed through less reliable infrastructure components. In some cases, there may be no fallback routes available in case of component failure. This paper provides a new technique for identifying critical components of an infras- tructure system, where a component is deemed criticalaccording to the role it plays in providingcriticallocationswithresources(i.e.,itsparticipationin criticalﬂows ). Whilethe critical infrastructure protection literature contains methods for identifying vulnerabilities innetworkscontainingcriticalassets(e.g.,[5]),thepresentmethodallowscriticalityratings topropagatethroughanetwork. Itisalsohighlygranular,intendedforuseinurbandecision support systems operating at a parcel level. Furthermore, by combining critical ﬂow with standard reliability techniques, one can visualize the portions of an infrastructure system that: (1) play a disproportionate role in delivering resources to critical locations, and; (2) lack backup/failsafe routes. 2 Of course, infrastructures do not exist in isolation. Interdependencies between infras- tructure systems are ubiquitous, leading to complex failure patterns that are much more diﬃcult to predict [4]. The resulting ‘systems-of-systems’ [16] are subject to additional risks that arise from the complex interaction of their component systems, including cas- cading failures [45]. Nevertheless, in the interests of brevity this paper focuses on a single infrastructure system at a single moment in time. Thestructureofthispaperisasfollows. SectionTwoprovidesbackgroundinformation on CIMs. Section Three introduces the concept of critical ﬂow. Section Four shows how critical ﬂow can be used to construct several new CIMs. Section Five provides a simple method for calculating probabilistic critical ﬂow measures. Section Six provides a comparison with other centrality measures, as well as a demonstration of how reliability analysis might be integrated with critical ﬂow modeling. 2 Background and Previous Work Many research communities have proposed component importance measures (“CIMs") [3] for infrastructure systems. Examples of CIMs include network eﬃciency [34], ﬂow vulnerability [42], and ﬂow capacity rate [38]. Of particular interest are the centrality measures, which are used to identify the most central components in a network [48, 9, 10, 30, 37]. Arranged in categories (e.g,. [46, 42]), these include: 1.Nearnessmeasures ,whichcalculateacomponent’scentralitybymeansofitsproxim- itytoothercomponents(e.g.,degreecentrality[37],closenesscentrality[8],residual closeness centrality [15], information centrality [29], and evidential centrality [55]). 2.Betweenness measures , which consider components to be central to the extent to which they stand between other components as intermediaries (e.g., shortest-path betweennesscentrality[20],general-pathbetweennesscentrality[25],loadcentrality [23], and random walk betweenness centrality [36]). 3.Dynamicalmeasures ,whichexaminebothtopologyanddynamicalprocessessituated on the network (e.g., ﬂow centrality [21], traﬃc load centrality [35], random walk centrality [39, 36], routing betweenness centrality [17], dynamical inﬂuence [28], eﬃciency centrality [54], and percolation centrality [44]). 3 2.1 Flow-based Centrality Measures Several centrality measures are based on the concept of network ﬂow, of which the most popular is the classical formulation of ﬂow centrality (“FC") [21]. It can be viewed as a hybrid that combines: (1) betweenness, and; (2) a representation of network dynamics. In particular, a node Eis considered to be betweenother nodesDandFto the extent that the maximumﬂowbetween DandFdependsonE. FCisdeﬁnedformallyasfollows: Deﬁnition 1: Flow Centrality Consideraﬂownetworkwithnodes +andlinks. ForDEF2+,let<DF be the maximum ﬂow between DandF, and let<DF¹Eºbe the maximum ﬂow between DandFthat depends on E. Then the ﬂow centrality of a node E2+is the degree to which the maximum ﬂow between all unordered pairs of nodes depends on E: ¹Eº=Õ D<F<E<DF¹Eº (1) Thismeasurecanbenormalizedbydividingtheﬂowthatpassesthrough Ebythetotalﬂow between all other pairs of nodes, yielding the percentage of ﬂow that depends on E: 0¹Eº=¹EºÍ D<F<E<DF(2) Sincetheanalysisofsupply/demandnetworksfocusesprimarilyontherelationbetween source and sink nodes, this paper introduces a narrower formulation of ﬂow centrality (and ofedge-ﬂow centrality [38]). The source-sink ﬂow centrality (“SSFC") of a nodeEis the degree to which the maximum ﬂow between all source and demand nodes depends on E: ((¹Eº=Õ B2(32B<3<E<B3¹Eº (3) where<B3is the maximum ﬂow between Band3, and<B3¹Eºis the maximum ﬂow betweenBand3thatdependson E. Thiscanbenormalizedbydividingtheﬂowthatpasses throughEby the total ﬂow between all pairs of source/sink nodes: 0((¹Eº=¹EºÍ B2(32<B3(4) 4 2.2 Flow-based CIMs Applied to Infrastructure Variousresearchcommunitieshaveappliedcentralitymeasurestothestudyofinfrastructure systems (see, for example, [33, 56, 13, 31]). Recent work has focused on dynamical CIMs, including those based on network ﬂows. Comparisons between topological and ﬂow-based methodologies have appeared in several recent studies (e.g., [58, 41, 42]). Probabilisticestimatesofreliabilityinaﬂownetworkareprovidedin[26]. Anetworkis deemedreliableto the extent that demand nodes have at least one path to the source, given component failures. To determine reliability, an appended spanning tree data structure is used to identify a set of disjoint spanning trees. For a given failure scenario, each of these spanning trees )8is inspected to determine if demand nodes have at least one path to the source. The results are then aggregated to create a measure of reliability for the scenario. Thenetworkisnotaproperﬂownetworkwithcapacities,buttheconceptoffallbackroutes is evident. Amethodforrankingvulnerabilitiesinadirected,capacitated,ﬂownetworkispresented in[32]. Damagescenariosarecreatedbydisablingoneoftheedges. Ascenarioisevaluated by determining its impact on the supply coverage (supply/demand ratio) at each sink. A greedy, path-based algorithm ﬁnds the geodesic with maximum capacity between a sink and a source, and reserves the demand from the sink against the capacity of each edge and vertexofthegeodesic. (Ifcapacityconstraintsareviolated,thereisasupplyproblemforthe givensink). Multi-attributedecisiontheoryisusedtocalculatethe disutilityofthescenario. Thereisnopriorityorderimposedonthenodes,noristhereconsiderationoffallbackroutes. A CIM for a directed, uncapacitated, ﬂow network is provided in [18]. To identify critical nodes: (1) a synthetic baseline network is generated, using nodal degree to identifyauniquesupplynodeandtoassigndemandvalues;(2)hydraulicsimulationisused to compute ﬂows; (3) a ‘roving supply node’ simulation is performed. In each iteration a singledemandnode 3isremovedfrom ,yielding f3g,andhydraulicsimulationis used again. After iterating through all demand nodes, a new supply node is chosen and the process is repeated until all combinations have been covered. The impact of each scenario 9isq ¹19º2¸¹29º2¸¸¹=9º2,where89isthediﬀerenceinﬂowfornode 8between and f8g. Unlike the present paper, the supply nodes are not ﬁxed, and no priority is imposed on demand nodes. A hierarchical approach to evaluating the robustness of capacitated ﬂow networks is described in [19]. A network is represented as a multi-level ﬂow model in which each demand node is assigned a priority level . Reliability evaluation is carried out through a MonteCarloapproach[57]inwhichasystemconﬁgurationiscreatedbysamplingthelink 5 capacities from their probability distributions. For each conﬁguration, a greedy, surplus- basedalgorithmpushesﬂowthroughthenetwork,satisfyinghigherprioritynodesﬁrst. The resultsfromnumeroussuchconﬁgurationsareusedtoestimatetheprobabilitydistributionof theamountofﬂowdeliveredtoeachdemandnodeatequilibrium. Thenetworkis robustto theextentthatsuﬃcientlevelsofﬂowreachthedemandnodesdespitecapacitydegradation ofthelinks. However,assigningﬂowbasedonnodepriorityismarkedlydiﬀerentfromthe method proposed in the present work. Flow-basedvulnerabilitymeasuresforacapacitatedanddirectednetworkaredeveloped in[38]. Themeasuresareusedtoidentifyasetoflistofnetworkedgesthatcanbehardened against damage from geographically-situated disruptions; Performance of the network is measured by computing an all-pairs average network ﬂow i¹Gºby means of a /m.sc/i.sc/n.sc/i.sc/m.sc/u.sc/m.sc /c.sc/o.sc/s.sc/t.sc /n.sc/e.sc/t.sc/w.sc/o.sc/r.sc/k.sc /f.sc/l.sc/o.sc/w.sc /a.sc/l.sc/g.sc/o.sc/r.sc/i.sc/t.sc/h.sc/m.sc [2]. Several edge importance measures are considered, including: (1) all-pairs max-ﬂow edge count , the total number of times a given edge is utilized in all BCpairs max-ﬂow problems, and; (2) edge ﬂow centrality : sum of ﬂow on the edge for all possible BCpair max-ﬂow problems, normalized by the sum of all- pairs max-ﬂows. No priority order is imposed on nodes, but the measures are important precursors for the work described in the present paper. Finally, a variant of current-ﬂow betweenness centrality [36] was applied to to urban networksin[1]. Sincethecomputationalcostofthistypeofcentralitymeasurecanbequite high, an approximation method is used to allow for its use on high density urban datasets. The authors use the new method to study pedestrian ﬂow on a dataset of 186 nodes that is drawn from a real-world street network in Spain. Priority order on nodes is not supported, butthemethodisausefulcomparatorasitisdesignedforanalyzingurbaninfrastructureat district scale. While this is not an exhaustive list of previous work on ﬂow-based CIMs, it is rep- resentative of basic techniques and guiding assumptions. Although various authors have proposed means of identifying critical components using ﬂow-based techniques, only one [19]permitsnetworkcomponentstobelabeledwithcriticalityvaluesofthesortcommonly usedincriticalinfrastructureprotection(e.g.,[5]). Inthatwork,thealgorithmforgenerating theﬂowsolutionensuresthathigherprioritynodesaresatisﬁedﬁrst. Incontrast,thepresent work does not make any such assumption, allowing a variety of techniques (e.g., hydraulic simulation) to be used in determining ﬂow solutions and the resulting centrality values. 6 3 Critical Flows This paper describes a means of modeling the impact of changes in demand, supply, or capacity on the distribution of ﬂows within a system. Of particular interest are critical ﬂows–ﬂows that deliver resources to critical locations such as hospitals. Components are deemedcriticalto the extent that they participate in critical ﬂows. For example, changes in demand can result in signiﬁcant changes to the distribution of ﬂows. PartofFigure 1 shows a capacitated network in which demand node 31has been deemed to be critical. Part shows a maximum ﬂow solution for the network; the ﬂow to31is balanced between the paths ¹(= 131ºand¹(= 231º, with each path carrying 75 unitsofﬂow. Furthermore,theﬂowtoalldemandnodesisapproximatelybalanced,andthe internal edge¹=1=2ºis not used. Aslightchangetothenetworkdrasticallyaltersthedistributionofcriticalﬂows. Part  ofFigure1 showsamodiﬁednetworkinwhichthedemandat 33hasbeenincreasedto 22. Partshows the resulting change in critical ﬂow patterns: the majority of ﬂow to critical location31isnowroutedthroughtheupperpath ¹(= 131º. Thiscanresultinincreasedrisk in cases where components in the upper path are unreliable or scheduled for maintenance. 3.1 Representing Criticality Themethodpresentedinthisworkrequiresamodelertoassign criticalityratings toassets. There are at least three options for modeling asset criticality: (1) a binary representation , in which an asset is either critical or not; (2) a categorical representation , in which an asset’scriticalityisselectedfromaﬁniteset(e.g., f;>F<4386g),and;(3)a continuous representation , in which an asset’s criticality is a real number. After the modeler has labeled assets with criticality ratings, the rest of the system’s components are evaluated. Each component is ranked according to its role in delivering resources to critical assets. There are several possible ranking methods for a component: (1)absolute critical ﬂow , the amount of critical ﬂow that passes through it; (2) percentage critical ﬂow , the percentage of its ﬂow that is critical; (3) location count , the number of critical locations that receive ﬂow from it, and; (4) weighted expected critical ﬂow , the expectedamountofresourcethatitsuppliestodemandnodes,weightedbytheircriticality. 7 A: S20 n1 d1d=15 n210 25 25 d325 d=8 d2 20 d=8 10 B: S20 / 15.5 n1 d1d=15 n210 / 7.5 25 / 15.5 25 / 7.5 d325 / 8 d=8 d2 20 / 8 d=8 10/ 0 Critical Critical C: S20 n1 d1d=15 n210 25 25 d325 d=22 d2 20 d=8 10 D: S20 / 20 n1 d1d=15 n210 / 10 25 / 2525 / 5 d325 / 22 d=22 d2 20 / 8 d=8 10/ 2 Critical Critical Fig.1.Acapacitatednetwork( )andamaximumﬂowsolution( )showingcriticalﬂows. Demandnode 31isdeemedacriticallocation. Capacitiesandﬂowvaluesaregivenas -. where-is the capacity and .is the ﬂow value, and demands are indicated as 3=G. () showsthesamenetworkas( ),butnode33hasgreatlyincreaseddemand. ( )showshow the upper path now carries the bulk of critical ﬂow to 31. 8 4 Component Importance Measures based on Critical Flows The concept of critical ﬂow may be used to deﬁne numerous CIMs. 4.1 Critical Flow Centrality The most intuitive critical ﬂow CIM is obtained by modifying the classical notion of ﬂow centrality [20]. A node is deemed centralto the extent that it is involved in the ﬂow of resources to critical locations. Examples of such measures include: 1.(Binary) Critical Flow Centrality : let+=f31323:gbe the set of demand nodes in that are deemed critical. and let (=fB1B2B?gbe the set of source nodes in . Let<B3be the maximum ﬂow between B2(and32. (In the case where there is a single source, this is the same as the ﬂow entering 3). Furthermore,givennode E2+2,let<B3¹Eºbethemaximumﬂowbetween Band 3thatdependson E. Thenthe (binary)criticalﬂowcentrality ofanodeE2+2 is the degree to which the maximum ﬂow between critical demand nodes and source nodes depends on E: ¹Eº=Õ B2(32<B3¹Eº (5) 2.Weighted Critical Flow Centrality : let the set of demand nodes in the network be =f31323<g, and consider function 2A:!R¸that maps a demand node 32to acriticality value 2A¹3º. Then the weighted critical ﬂow centrality of a nodeE2+is: ,¹Eº=Õ B2(322A¹3º<B3¹Eº (6) Both of these CIMs may be normalized by the total critical ﬂow on the network. 4.2 Probabilistic Critical Flow Measures Themeasuresintroducedabovearebasedonmaximumﬂows. Onecanrelaxthisassumption. Consider demand nodes =f31323<g, and criticality function 2A:!R¸. Let Dbe a family of functions X8:!R¸, each of which assigns a demandX¹3º2R¸for eachdemand node 32. Finally,let an assignment bea concretechoiceof function X8 fromD, and let5¹3ºbe theﬂow received by32under. 9 Theﬂowin network given assignment is the aggregate of all ﬂows reaching the demand nodes: ¹ º=Õ 325¹3º (7) Thecritical ﬂow in network given assignment is the set of ﬂows reaching the demand nodes, weighted by criticality rating 2A:  ¹ º=Õ 325¹3º2A¹3º (8) Let5¹E839ºbe the ﬂow that reaches 392from/through node E82+under assignment. The main quantity of interest is the expected amount of ﬂow from E8that reaches39: »5¹E839º¼ (9) This leads to the following deﬁnition (stated for vertices): Deﬁnition 2: Vertex CFC The (probabilistic) critical ﬂow centrality (“CFC") of a vertex E2+is: %¹Eº=Õ 322A¹3º»5¹E3º¼ (10) The CFC of vertex Eis the sum of all expected amounts of ﬂow being delivered via Eto the demand nodes, weighted by their criticality. The CFC may be normalized by an appropriateexpression,suchasthetotalﬂow ¹ ºorthetotalﬂowweightedbycriticality  ¹ º: 0%¹Eº=%¹Eº  ¹ º=Í 322A¹3º»5¹E3º¼Í 322A¹3º5¹3º(11) Variations on these formulas are easy to construct. First, identical deﬁnitions can be formulatedforedges. Second,onecanconcoctunweightedversionsinordertoaccommodate thebooleanrepresentationofcriticality. Third,additionalfactorsmaybeincorporated(e.g., reliability estimates for components, as discussed in Section 6.2). Lastly, these deﬁnitions are compatible with the use of utility functions , although that topic is not discussed in this paper. 10 5 Computing the Critical Flow Measures TheprevioussectionprovideddeﬁnitionsofnewCIMs,butnoguidanceonhowtheyareto be computed. This section presents a general framework for doing so, as well as a simple instantiation that computes the (probabilistic) critical ﬂow centrality (“CFC"). 5.1 A Method for Critical Flow Analysis The framework for computing critical ﬂow CIMS involves four elements: 1. a representation of an infrastructure system as a ﬂow network; 2. input data (i.e., demand values, criticality ratings, capacity constraints); 3. a means of calculating ﬂows, and; 4. a means of determining the probability that a given network component (node, link) carries ﬂow to a given demand node. Sincetheseelementscanbesuppliedindiﬀerentways,therearemanypossibleinstantiations ranging from simple to highly complex. This paper presents a simple version for clarity. 5.2 Network Representation Aninfrastructuresystemisrepresentedasaweighted,capacitated,ﬂownetwork =h+i where+is a set of nodes, and ++is a set of links. Each node E2+hasworld coordinate®F¹Eº=¹EGEHEIº2R3. Each link4=¹E8E9º2has acapacity2¹4º2N and aﬂow5¹4º2N. Bi-directional relationships, cycles, and self-loops are all permitted. Thenetwork containsbothsource(supply)andsink(demand)nodes. Thesetof source nodesis(=fB1B2B?g+,andthesetof demandnodes is=f31323<g2+. All other nodes are called transmission nodes . Aﬂowon is a real-valued function 5:!Ron ’s links that obeys three ﬂow properties: 1.Capacity Constraints : for all4=¹E8E9º2, we have5¹4º2¹4º. 2.Skew Symmetry : for all4=¹E8E9º2, we have5¹¹E8E9ºº=5¹¹E9E8ºº. 3.Flow Conservation : for all nodes EC2+¹[(º, we haveÍ E2+5¹¹ECEºº=0. Thevalue of a ﬂow is deﬁned as the ﬂow exiting the source nodes: j5j=Í E2+5¹BEº. While a network with multiple source and sink nodes may be reduced to a network with a single sink and source, (see [14]), the explicit representation is used throughout this paper. 11 5.3 Demand Distributions and Criticality The basic network ﬂow model is augmented with additional metadata. First, a demand functionX:!Nmaps a demand node 32to a demand X¹3º. Second, a supply constraint function 5B:(!Nassigns each source node B2(a maximum ﬂow 25¹Bº. Third, acriticality function 2A:!»01¼maps32to a criticality rating 2A¹3º between 0and1. Anassignment to a network involves assigning supply constraints to all source nodes and criticality/demand values to all demand nodes. These values may be provided by simulation (e.g., stochastic processes) or via external data. 5.4 Calculating Network Flow For a given assignment to the network, a network ﬂow must be computed. While binary andcategoricalrepresentationsofcriticalitycanbeaccommodatedusinga multi-commodity network ﬂow algorithm [2], the continuous representation of criticality requires the use of alternative techniques, including: (1) general network ﬂow algorithms, or; (2) domain- speciﬁc simulation techniques (e.g., hydraulic simulation [40]). The most intuitive way to create a ﬂow on an network is to utilize an algorithm for the/m.sc/a.sc/x.sc/i.sc/m.sc/u.sc/m.sc /f.sc/l.sc/o.sc/w.sc /p.sc/r.sc/o.sc/b.sc/l.sc/e.sc/m.sc [2]. A major drawback to this approach is that popular maxﬂow algorithms do not yield network ﬂows that are balanced across competing paths. (Algorithms that allow for disjunctive constraints exist, as in [43], but they have some drawbacks). Domain-speciﬁc methods are preferable in cases where a realistic ﬂow must be obtained. For simplicity, this paper uses the the Edmonds-Karp algorithm [see [14]]. 5.5 Calculating Critical Flow from Flow Patterns Once a ﬂow solution has been obtained for assignment , the CIM can be computed. In the case of the CFC measure, one must compute »5¹2839º¼(Equation 9 ), the expected amountofﬂowpassingthroughcomponent 28thatendsupatdemandnode 39. Foramodel that uses empirical data, a sampling approach is required. The demonstration method in this paper represents an infrastructure system at a single point in time using integer-valued demands, so that Equation 9 is equivalent to the probability that a unit of ﬂow passing through28ends up at39, multiplied by the total amount of ﬂow passing through 28: »5¹2839º¼=%¹39j28º5¹28º 12 Therequiredprobabilitiescanbecomputedinseveralways. Themostintuitiveapproach is to reduce the problem to Markov chain computation [49, 50]. Another feasible solution is to estimate probabilities from the ﬂow network using a Time Forward Random Walk [7]. In contrast, the present instantiation uses a graph search approach to directly compute the probability for each node E(or link4) that a unit of resource passing through E(or4) lands in a given demand node 3.Figure 2 shows how this is performed for a demand node corresponding to a lot/parcel. 3.7 3.33.33.7 3.33.73.77 3.3 3.3 3.33.73.7 3.3 77 3.33.73.77 3.3 3.3 3.33.7 7 7 7 Fig. 2.Calculation of expected amount of ﬂow delivered from source (green) to a demand node (black). Nodes/links that do not supply resources to the demand node are not shown. The ﬂow solution is transformed into a secondary transition graph 0that represents the ﬂow in terms of transition probabilities. Every node in 0contains a list of outgoing links,eachofwhichislabeledwiththeprobabilitythataunitofﬂowissentdownthatlink. (If a link in the ﬂow network has a ﬂow of 0, it does not appear in 0). The edges in 0 are unidirectional. Demandnodes 32intheoriginalﬂownetwork arereferredtoas absorbingnodes in 0. Associated with every non-absorbing node E82 0(and every link 482 0) is a mapdatastructure E8<0?(or48<0?)thatstorestheentiresetofdemandnodesreachable fromE8(or48). Eachentryinthismapcontainsanidentiﬁerofademandnode 39,together withtheprobability %¹39j28ºthataunitofﬂowwillreach 39fromthenode/link 28towhich the map belongs. Metrics can be computed by examining the contents of the map and the 13 attributes of the relevant absorbing/demand nodes. The method for computing conditional probabilities is shown in Algorithm 1 . It proceedsbyexploringsecondarygraph 0inreverse,tracingoutpathsfromeachabsorbing node32to a source. For each 3, a search of the graph is performed by following incoming edges 4=¹BA23BC?A>1018;8CH º, recording the probability of arriving at 3at each subsequent component. Function ComputeProbabilities(G’) Data:G’, a graph with components ¹+ºand absorbing nodes +. foreach32do ReverseSearch (G’, d) end Function ReverseSearch(G’, d) Data:G’, as above. Data:d, an absorbing node. Var excess[] // array of numbers 2»01¼of sizej+j Var stack excess[d.ID] = 1 stack.push(d) whilestack not empty do Var curNode = stack.pop() Var amt = excess[curNode.ID] // amount of probability to push foreachincoming edge curEdge of curNode do curEdge.map.IncrementOrAddProbability(d.ID, amt) excess[curEdge.src.ID] = amt * curEdge.probability stack.push(curEdge.src) end curNode.map.IncrementOrAddProbability(d.ID, amt) excess[curNode.ID] = 0 end Algorithm 1: A Deterministic Algorithm for Computing Flow Probabilities. A lookup table containing probability values for each node is maintained in a helper variable4G24BB, indexed by node ID. The IncrementOrAddProbability () function updates the estimate of %¹3j2ºstored in the map of component 2. The lookup table and variable amtare used to avoid problems with overlapping paths. Oncetherelevantprobabilitieshavebeendetermined,theCFCofacomponent 28(edge or node) is computed as: %¹28º=Õ 39228<0?%¹39j28º2A¹38º5¹28º (12) 14 where39isademandnode, %¹39j28ºistheprobabilitythatﬂowpassingthrough 28reaches 38,5¹28ºis the ﬂow passing through 28under assignment , and2A¹38ºis the criticality of38. The measure may be normalized by the maximum CFC value for the network. For vertices, this gives: 0%¹E8º=Í 382E8<0?%¹38jE8º2A¹38º5¹E8º maxE2+¹%¹Eºº(13) Figure 3 shows the four stages of computation. A model consists of a planar region containing blocks(lightpurple). Eachblockmaycontainabuilding(darkpurple)orasetof lots (lightgreen) representinghouses. Awater distributionnetwork provides buildingsand lots with water drawn from a reservoir. The basic topology of the street and water network is taken from downtown Toronto, while demand values for buildings and lots are sourced from empirical studies [6]. The modeler assigns criticality values to buildings manually. The basic network model is shown in the upper left, along with demands for each lot/building (black font). The upper right diagram shows a ﬂow solution computed on the basic network, while the lower left shows the induced probability graph arising from this ﬂow. (Network edges with zero ﬂow are elided from the probability graph). Finally, the lower right diagram shows the critical ﬂow metrics, ranging from green (low criticality) to red (high criticality). Criticality ratings for buildings are in white font. 5.6 Computational Requirements Algorithm 1 is quadratic in space and time. In the worst case, the map at each node/link storesjjentries,oneforeachdemandnodeinthenetwork,leadingto $¹¹j+j¸jjºjjºin storage space. As a variant of depth ﬁrst search, the time required to compute probabilities for each demand node is $¹j+j¸jjº, so the total time required for all demand nodes is again$¹¹j+j¸jjºjjº. For infrastructure networks, j+jjjandjj/1 2j+j, yielding time and space complexity bounds of $¹j+j2º. For the model used in this paper, the maps atnodes/linkscontainanaverageof 5entrieseach,pushingthestoragerequirementscloser to$¹j+jº(seeFigure 4). The running time of the entire method is dominated by the $¹j+jjj2º  ¹j+j3º Edmonds-Karp algorithm that is used to generate ﬂows. If a push-relabel algorithm is used, the running time can be reduced to $¹j+j2p jjº$¹j+j2p j+jº. In contrast, be- tweenness centrality [20] can be computed in $¹j+j3ºusing the Floyd-Warshall algorithm or$¹j+j2logj+j¸j+jjjº$¹j+j2logj+jºtime using Johnson’s or Brandes’ algorithm (see [14]). 15 200087777787778 77888778778 88886888878787 877787 8 7878788787 7 7 7 788887 8877687887887887877878787 78778778776 8 12007 890 7 8 source120 900 3000600 60025 600600 150150132 4046 538 554 15 4595 2486 1200 1674 5434 1000 2000 4595 1206 4595 4702 2000 5500 5434 600 5380 662 600 600 15 1171 604 15 4595 334 4536 4380 15 1074 3956 600 1200 600 4486 1025 10802 1051 942 1806 2000 96 0.50.5 1 0.27 0.730.53 0.47 1 0.990.55 0.45 0.85 0.150.560.440.96 0.980.0220.980.060.9410.12 0.88 0.190.81110.94 1 10.97 0.530.47 11 0.0110.99 0.44 0.5110.991 0.720.28 111 1 10.920.0760.490.51 1 1 0.990.10.9 0.045 0.96 10.67 0.330.013 0.50.50.360.640.11 0.64 0.045 0.042 0.17 0.15 0.1 0.097 0.79 0.12 0.42 0.17 0.21 0.17 0.0037 0.17 0.42 0.79 0.79 0.042 0.79 0.056 0.042 0.042 0.21 0.045 0.17 0.028 0.17 0.67 0.084 0.64 0 0.042 0.1 0.042 0.16 0.22 10.21 0.22 0.42 0.02 0.6 0.02 0.2 0.4 10.7 0.1 0.2 0.1 0.1 0.02 0.02 Fig.3.Fourstepsincriticalﬂowcomputation. Upperleft: networktopologywithdemands. Upper right: maximum ﬂow. Lower left: induced probability graph. Lower right: critical ﬂow (CFC), with light green being non-critical and red being critical. 16 0 20 40 60 80 100 120 Map size0255075100125150175200CountFig. 4.Distribution of sizes for the map data structures in the model shown in Figure 3. Almost all of the nodes/links have a map with less than 6 entries. Note that Algorithm 1 does not work for a transition graph 0that contains cycles. TheEdmonds-Karpalgorithmdoesnotcreatecycles,butthisisnotnecessarilythecasefor domain-speciﬁc methods. For ﬂow networks with cycles, alternative techniques must be used. 5.7 Sampling Variants This paper presents a ‘one shot’ scenario in which a single set of integer-valued demand values is used. »5¹2839º¼, the expected amount of ﬂow from component 28to demand node38,iscomputedwiththeuseofaconditionalprobability %¹39j28º. Ifempiricaldatais available,orifdemandvaluesaresampledfromprobabilitydistributions,thebasicmethod must be adapted to support sampling. This is accomplished easily with a modiﬁcation that iterates over input data sets and computes »5¹2839º¼as a sample mean of conditional probabilities. 17 6 Evaluation The utility of the critical ﬂow method presented in this paper is demonstrated in two ways: (1) comparison with alternative ﬂow centrality measures, and; (2) integration with two common forms of reliability analysis. 6.1 Comparison with Flow Centrality Measures The FC, SSFC, and CFC measures were computed for a small model that was patterned after high density neighbourhoods in Toronto, Canada. Figure 5 shows four views of this basicmodel. Theupperleftviewshowsthemodelandthedemandsateachbuildingandlot. Theﬂowresultingfromthisconﬁgurationisshownintheupperright,whereblacknetwork edges indicate that no ﬂow is present. In the lower left, the SSFC centrality measure has beencomputedforeachedgeandvertex. ThelowerrightshowstheFCcentralitymeasure. TheFCmeasureplacesemphasisonthecentralnodesinthegraph,leavingthesoleedge emanating from the source (i.e., the most critical) relatively dark. In contrast, the SSFC is highly correlated with the ﬂow, as shown in Figure 6. The fact that both the SSFC and the maximum ﬂow have occasional black edges is an artifact of the Edmonds-Karp algorithm. Figure7(A) showsthecriticalﬂowforthesamemodelanddemand/criticalityconﬁgu- ration. Criticalitylevelsforbuildingsaredisplayedinwhitefont;lotcriticalityisnegligible andelided. Thecriticalﬂowcomesfromthehospital( 1),school( 06ºandpublicbuildings (02) down the right of the network. Figure 7(B) arises from a single modiﬁcation: the demand on one of the non-critical buildings is raised from 150 to 2000. This forces a redistributionofﬂowsonthenetworkduetocapacityconstraintsontherighthandpath. As a result, critical ﬂow is more evenly balanced across all paths from the source. The SSFC and FC measures are unable to capture the ﬂow redistribution involved in Figure7. ToalargeextentthisisaresultofSSFCandFCbeingbasedonsumsofmaximum ﬂows between subsets of +(i.e., pairs in the case of FC, sources and sinks in the case of SSFC).Sincetheunderlyinggraphisonlychangingslightlybetweenscenario(A)and(B)of Figure7,theSSFCandFCmeasureschangeonlyslightly. Incontrast,theCFCiscomputed onaper-ﬂowbasis,wheretheﬂowinquestionistheresultofcompetitionbetweendemand nodes for supply. The CFC is therefore a measure of not only the network’s topology, but also theloadinduced by an assignment of supply, demand, and capacity values. 18 200087777787778 77888778778 88886888878787 877787 87878788787 7 7 7 788887 8877687887887887877878787 78778778776 8 1200 7 890 7 8120 900 3000600 60025 600600 150150Hospital SchoolFig. 5.Comparison of centrality measures. Upper left: empty network showing demands. Upper right: ﬂow upon the same network. Lower left: source-sink ﬂow centrality (SSFC). Lower right: Freeman’s ﬂow centrality (FC). The darker an edge, the lower the centrality score. (Pure black edges have no data).19 Fig. 6.Correlations between CIMs on the network in Figure 5. Normalized ﬂow (FLOW), normalizedprobabilisticcriticalﬂow(PCF_NORM),normalizedsource-sinkﬂowcentrality (SSFC_NORM), and normalized ﬂow centrality (FC_NORM). Diagonal elements show kernel density estimators for each CIM. 20 0.00014 0.36 0.40.390.0940.28 0.50.11 0.40.0057 0.4 0.40.27 0.50.50.50.1 0.40.023 0.4 0.380.27 0.360.0013 0.0990.21 0.0990.12 0.390.2 10.120.0025 0.0170.380.00011 0.650.078 0.120.110.088 0.80.120.42 0.120.22 0.12 0.12 0.80.80.0750.80.023 0.0750.22 0.120.0280.12 0.680.076 0.65 0.0750.1 0.0750.120.22 10.22 0.230.42 0.02 0.60.020.20.4 10.70.10.2 0.1 0.1 0.020.020.076 0.0750.0780.2 0.2 0.27 0.096 0.0088 0.0032 0.0990.099Increased demand A B 0.1 0.1Fig. 7.CFC measures. A: identical model and demand/criticality conﬁguration to that in Figure 5. Criticality levels for buildings are show in white, while lot criticality is ﬁxed at 0.05. Critical ﬂow favors the right side of the network. B: a variation in which a single buildinghashaditsdemandraisedfrom150to2000. Flowpatternsarechangeddrastically, with critical ﬂow being redistributed across the network. Black edges have no data, light green edges are non-critical, and red edges are critical. 21 6.2 Edge Reliability The critical ﬂow measures introduced in this paper may be combined with reliability esti- mation procedures (e.g., edge reliability [56]). As a simple example, a reliability function A:!»01¼can be used to assign edges 42a reliability rating A¹4º. Edges with high criticalityandlowreliabilitycanbeidentiﬁedbyusingthe ReliableCriticalFlow (“RCF") CIM: 0'¹4º=0%¹4ºA¹4º (14) Since both the normalized CFC and reliability ¹4ºlie in the interval»01¼, the same is truefor0'¹4º. Reliabilityvaluescanbeobtainedthroughavarietyofmeans,including surveys,inspections,orinferencesfromthephysicalcharacteristics(e.g.,age)oftherelevant components. Diagram A of Figure 8 shows reliability values for the model in Figure 3. Diagram B is a plot of edge reliability versus CFC. The majority of the edges have negligible CFC (e.g., those edges that feed individual lots). The solitary edge with a criticality of 10is the edgefromthereservoirthatcarriesﬂowfortheentiremodel. Ofparticularinterestarethose edges that have lower reliability ratings and moderate criticality. While edge reliability can be combined with FC, SSFC or other centrality measures, the use of the CFC provides a snapshot of the actual critical load on the network under a given assignment. Combining the FC measure with edge reliability, for instance, allows components to be ranked according to their role in facilitating maximum ﬂows between all pairs of vertices, weighted by reliability. While this might be useful for social networks in whichinformationﬂowsarbitrarily,itdoesnotmatchthetypicalloadpatternsonsource/sink networks. 6.3 Component Failure Analysis Criticalﬂowmeasuresalsosupportacommonformofreliabilityanalysisinwhichcompo- nentsarefailediterativelyinordertoascertaintheimpactontheglobalperformanceofthe network (e.g., [18]). The total amount of critical ﬂow (i.e., the ﬂow delivered to demand nodes, weighted by criticality) can be used as a performance measure. Each edge/node can befailediterativelyina‘leaveoneout’analysis,andtheimpactontotalcriticalﬂowcanbe recorded. Thistypeofanalysiscanbeusedtoidentifycomponentsthatlackfallbackroutes. Figure 9 shows the result of using this approach on the edges of the network in Figure 5. Thevastmajorityofedgescarrylittlecriticalﬂow,andthereforehaveinsigniﬁcantfailure loss. More interesting are the edges on the upper left, with moderate CFC and no failure 22 A B Fig.8.Edgeunreliabilityandcriticalﬂow. DiagramAshowsedgereliabilitylevels,ranging from green (reliable) to red (unreliable). Diagram B plots corresponding reliability values against critical ﬂow values (taken from Diagram A of Figure 7). 23 0.0 0.2 0.4 0.6 0.8 1.0 Failure Loss0.00.20.40.60.81.0CFCFig. 9.CFC and failure loss values for edges. loss. These are edges for which there are backup routes available (e.g., the edges in the residentialblocks). Theedgeintheupperrightistheedgeincidentonthelonesourcenode, the failure of which is catastrophic. 7 Conclusion Thispaperintroducedasetof componentimportancemeasures (“CIMs")basedonthecon- cept of critical ﬂow. The motivation for the work was to provide urban planners and other stakeholders with a means of visualizing the impact of capacity-related changes on infras- tructure systems. Various internal and external events (e.g., zoning decisions, population growth, maintenance, component degradation) can aﬀect the distribution of ﬂows within the system. In extreme cases, these events may interfere with the delivery of resources to critical locations such as hospitals. TheCIMspresentedinthisworkrepresentaninfrastructuresystemasaﬂownetworkin which the demand nodes are augmented with criticality ratings. Components in the system are deemed criticalto the extent that they facilitate the delivery of resources to critical 24 nodes. The paper showed how to use the critical ﬂow centrality (“CFC") measure to rank components. After criticality values were assigned to the demand nodes, a probabilistic algorithmwasusedtopropagatecriticalityratingsthroughtheentirenetwork. Althoughthe algorithmusedinthepaperwasdiscrete,awidevarietyoftechniquescanbeaccommodated (e.g., simulation). The CFC measure was compared against two versions of ﬂow centrality (“FC") on a small, but realistic, model. The CFC was able to identify shifts in ﬂow distribution that arise from changes in both demand and network topology. In contrast, FC aggregates maximalﬂowsgeneratedbetweenpairsofvertices,resultinginameasurethatlargelytracks the topology of the network. The CFC is speciﬁc to a particular ﬂow solution–that is, it represents the system under a particular load. When paired with reliability methods, it allows a modeler to identify critical nodes that lack fallbackroutes. The methods in this paper were designed to aid municipalities in reasoning about the consequences of interventions. For instance, they could be used in GIS software in order to help urban planners consider the impacts of zoning decisions (e.g., densiﬁcation). Maintenance engineers could also use them when developing schedules for the repair of infrastructure components, since: (1) highly critical components should be serviced more frequently, and; (2) repairing one set of components can shift critical ﬂow across the network, potentially introducing new risks. Finally, components that lack fallback routes require particular attention. The approach shown in this paper is only a simple instantiation of a general method, providing a basic means of generating ﬂows and computing probabilities. Future work shouldinvestigatetheuseofdomain-speciﬁcmethods,aswellasapproachesforcomputing probabilities that work with cyclic transition graphs. Perhaps the most urgent need is to apply critical ﬂow measures to a system that evolves over time. There are many additional avenues for future research. First, performance measures could be introduced to yield a metric that enables comparison and optimization. Second, transmission vertices could be given capacity constraints, and transmission nodes/edges could be augmented to act simultaneously as supply or demand nodes (e.g., edges could be given a small loss to model component degradation). Third, network clustering algorithms (see [12]) could be introduced to reduce the number of demand nodes. Lastly, one could extendthemethodtoidentifygroupsofcriticalcomponents(e.g.,criticalpathsorclusters). 25 7.1 Data Availability Statement Some data, models, or code generated or used during the study are available from the corresponding author by request: (1) ESRI CityEngine lot/parcel geometry and network topology in XML format; (2) Python scripts to extract lot/parcel geometry and network topology from CityEngine; (3) CityEngine scene ﬁle for the sample city used in the paper, and; (4) C++ source code for the probability propagation algorithm.