Random Walk Fundamental Tensor and Its Applications to Network Analysis
Golshan Golnari Zhi-Li Zhang Daniel Boley
cs.DM cs.SI

































Department of Computer Science and Engineering, University of Minnesota


We first present a comprehensive review of various Markov
metrics used in the literature and express them in a consistent framework. We then introduce fundamental
  tensor – a generalization of the well-known fundamental matrix –
and show that classical Markov metrics can be derived from it in
a unified manner.  We provide a collection of useful relations for Markov
metrics that are useful and insightful for network studies.  To
demonstrate the usefulness and efficacy of the proposed fundamental tensor in
network analysis,  we present four important applications: 1)
unification of network centrality measures, 2) characterization of
(generalized) network articulation points, 3) identification of
network most influential nodes, and 4) fast computation of network reachability after failures. 










Markov chain, random walk, fundamental tensor, network analysis, centrality measures, articulation points, influence maximization, network reachability














§ INTRODUCTION

Random walk and Markov chain theory, which are in close relationship, shown to
be powerful tools in many fields from physics and chemistry to social sciences, economics,
and computer science <cit.>. For network analysis, too, they have shown
promises as effective tools <cit.>, where the hitting time, a well-known Markov metric, is used to measure the distance (or similarity) between different parts of a network and provide more insight to structural properties of the network. We believe though that the applicability of Markov chain theory to network analysis is more extensive and is not restricted to using the hitting time. Markov chain theory enables us to provide more general solutions which cover the directed networks (digraphs) and is not tailored only to special case of undirected networks.   
 





In this paper, we revisit the fundamental matrix in Markov chain theory <cit.>, extend it to a more general form of tensor representation, which we call fundamental tensor, and use that to tackle four interesting network analysis applications. Fundamental tensor F_smt is defined [Note that the fundamental matrix is mostly denoted by N in Markov chain theory literature, but since N might reflect other meanings in computer science venues, we usually use F (or F to denote the tensor) in our papers. ] over three dimensions of source node s, middle (medial) node m, and target node t, which represents the expected number of times that the Markov chain visits node m when started from s and before hitting t for the first time.
We remark that the (absorbing) fundamental matrix which is frequently referred to in this paper is different from (ergodic) fundamental matrix <cit.> and is of special interest of the authors of this paper as: 1- it is nicely interpretable in terms of random walk, 2- it is conceptually interesting as aggregation over the (absorbing) fundamental tensor dimensions would result to different Markov metrics (Section <ref>) and the articulation points of a network can be directly found from it (Section <ref>), 2- it can be used for both applications that are modeled by an ergodic chain (Sections <ref> and <ref>) and applications modeled by an absorbing chain (Sections <ref> and <ref>), 3- it is easily generalizable to absorbing Markov chain with multiple absorbing states (Section <ref>) which we use to model network applications with multiple target nodes.
We show that computing the (absorbing) fundamental tensor is no harder than computing the (ergodic) fundamental matrix (O(n^3)) as the entire tensor can be computed very efficiently by a single matrix inversion and there is no need to compute the (absorbing) fundamental matrices for each absorbing state to form the entire tensor (which could take O(n^4) of computations).

As the first application, we show that the fundamental tensor provides a unified way to compute the random walk distance (hitting time), random walk betweenness measure <cit.>, random walk closeness measure <cit.>, and random walk topological index (Kirchhoff index)<cit.> in a conceptual and insightful framework: hitting time distance as the aggregation of the fundamental tensor over the middle node dimension, betweenness as the aggregation over the source and target nodes, closeness as the aggregation over the source and middle node dimensions, and Kirchhoff index resulted as the aggregation over all the three dimensions.  
These four random walk measures are of well-known network analysis tools which have been vastly used in the literature <cit.>.

In the second application, we extend
the definition of articulation points to the directed networks which has been originally defined
for undirected networks, known as cut vertices as well. We show that the (normalized) fundamental tensor nicely functions as a look up table to find all the articulation points of a directed network. Founded on the notion of articulation points, we also propose a load balancing measure for the networks. Load balancing is important
for network robustness against targeted attacks, where the balance in the loads help the network to show more resilience toward the failures. Through extensive experiments, we
evaluate the load balancing in several specific-shaped networks and real-world networks.

The applicability and efficiency of the fundamental tensor in social networks is the subject of the third application in this paper. We show that the (normalized) fundamental tensor can be used in the field of
social networks to infer the cascade and spread of a phenomena or an
influence in a network and derive a formulation to find the most
influential nodes for maximizing the influence spread over the
network. While the original problem is NP-hard, we propose a greedy algorithm which yields a provably near-optimal 
solution. We show that this algorithm outperforms the state-of-the-art as well as the centrality/importance measure baselines in maximizing the influence spread in the network. 

Since it is inefficient to use the regular reachability methods in large and dense networks with high
volume of reachability queries whenever a failure occurs in the network, devising an efficient dynamic reachability method is necessary in such cases. As the fourth application, we present a
dynamic reachability method in the form of a pre-computed oracle which is cable of answering
to reachability queries efficiently (O(1)) both in the case of having failures or no failure
in a general directed network. This pre-computed oracle is in fact the fundamental matrix computed for the extended network G^o and target o. The efficiency of the algorithm is resulted from the theorem that we prove on incremental computation of the fundamental tensor when a failure happens in the network. The storage requirement of this oracle is only O(n^2). 
Note that in the last two applications, the directed network G does not need to be strongly connected, and our algorithms can be applied to any general network. 

For the sake of completeness, we also provide a comprehensive review of the other Markov metrics, such as hitting time, absorption probability, and hitting cost, which is a very useful metric for weighted networks and was introduced in a more recent literature <cit.>, but can be rarely found in Markov chain literature. In the review, we include Markov metrics' various definitions and formulations, and express them in a consistent form (matrix form, recursive form, and stochastic form). We also show that the fundamental tensor provides a basis for computing these Markov metrics in a unified manner. In addition, we review, gather, and derive many insightful relations for the Markov metrics. 



 
 

 

 


The remainder of this paper is organized as follows. A preliminary on
network terminology is presented in Section <ref>.   In
Section <ref>, we review and present various Markov metrics
in  a unified format. In Section <ref>, we gather and
derive useful relations among the reviewed Markov metrics. Finally, four applications are presented in
Sections <ref>, <ref>, <ref>, and <ref>  to demonstrate the usefulness and
efficacy of the fundamental tensor in network analysis.  





§ PRELIMINARIES
 
In general, a network can be abstractly modeled as a weighted and directed graph, denoted by
G=(𝒱,ℰ,W). Here 𝒱 is the set of
nodes in the network such as routers or switches in a communication
network or users in a social network, and its size is assumed to be
n throughout the paper |𝒱|=n;  ℰ is the set
of (directed) edges representing the (physical or logical)
connections between nodes (e.g., a communication link from a node i
to a node j) or entity relations (e.g., follower-followee relation
between two users). The  affinity (or adjacency) matrix
A=[a_ij] is assumed to be nonnegative, i.e., a_ij≥ 0,
where a_ij>0 if and only if edge e_ij exists,
e_ij∈ℰ. The weight (or cost) matrix W=[w_ij] represents the costs assigned to edges in a weighted network. Network G is called strongly connected if
all nodes can be reachable from each other via at least one path. In this
paper, we focus on strongly connected networks, unless stated
otherwise.  

A random walk in G is modeled by a discrete time Markov chain,
where the nodes of G represent the states of the Markov chain. The target node in the network is modeled by an absorbing state at which the random walk arrives it cannot leave anymore.
The Markov chain is fully described by its transition probability
matrix: P = D^-1A, where D is the diagonal matrix of
(out-)degrees, i.e., D=diag[d_i] and d_i=∑_ja_ij. The d_i is
often referred to as the (out-)degree of node i. Throughout the
paper, the words “node" and “state",  “network" and “Markov
chain" are often used interchangeably depending on the context. If the network G is strongly
connected, the associated Markov chain is irreducible and the
stationary probabilities π are strictly positive according to
Perron-Frobenius theorem <cit.>. For an undirected
and connected G, the associated  Markov chain is reversible and the
stationary probabilities are a scalar multiple of node degrees:
π_i=d_i/∑_i d_i.  


    



§ DEFINITIONS OF MARKOV METRICS
 
 We review various Markov metrics and present them using three unified forms: 1) matrix form (and in terms of
 the fundamental matrix), 2) recursive form, and 3) stochastic form.
The matrix form is often the preferred form in this paper and we
 show how two other forms can be obtained from the matrix form. The stochastic form, however, provides a more intuitive definition
 of  random walk metrics. We also introduce fundamental tensor
 as a  generalization of the fundamental matrix and show how it can be computed efficiently.  
  


 §.§ Fundamental Matrix
 

The expected number of visits
counts the expected number of visits at a node, when a random walk
starts from a source node and before a stopping criterion. The
stopping criterion in random walk (or Markov) metrics is often “visiting a target
node for the first time” which is referred to as hitting
the target node. Fundamental matrix F is formed for a specific target node, where the entries are the
expected number of visits at a medial node starting from a source
node, for all such pairs. In the following, the fundamental matrix 
is defined formally using three different forms. [The fundamental matrix that is referred to in this paper is defined for absorbing chain and is obtained from F=(I-P_11)^-1. It is different from the fundamental matrix Z=(I-P+1π')^-1 which is defined for ergodic chain <cit.>.]




  * Matrix form <cit.>:
Let P be an n × n transition probability matrix for a strongly connected network G and node n be the target node. If the nodes are arranged in a way to assign the last index to the target node, transition probability matrix can be written in the form of P=[
[  P_11  p_12; p'_21  p_nn ]] and the fundamental matrix is defined as follows:

    F=(I-P_11)^-1,

where entry F_sm represents the expected number of visits of medial node m, starting from source node s, and before hitting (or absorption by) target node n <cit.>. Note that the target node can be any node t which would be specified in the notation by F^{t} to clarify that it is computed for target node t. 
This is discussed more in Markov metrics generalization to a set of targets (<ref>).

Expanding F_sm as a geometric series, namely,  F_sm=[(I-P_11)^-1]_sm=[I]_sm+[P_11]_sm+[P_11^2]_sm+..., it is easy to see the probabilistic interpretation of the expected number of visits as a summation over the number of steps required to visit node m.  



  * Recursive form: Each entry of the  fundamental matrix,
  F_sm,  can be recursively computed in terms of the entries of
  s's outgoing neighbors. Note that if  s=m, F_sm is
  increased by 1 to account for X_0=m (the random walk starts at
  s=m, thus counting as the first visit at m).  


    F_sm=1_{s=m}+∑_j∈𝒩_out(s) p_sjF_jm

It is easy to see the direct connection between the recursive form and
the matrix form: from F=I+P_11F, we have F=(I-P_11)^-1.  


  * Stochastic form <cit.>:
Let G=(X_k)_k>0 be a discrete-time Markov chain with the
transition probability matrix P, where X_k is the state of Markov
chain in time step k. The indicator function
1_{X_k=m} is a Bernoulli random variable, equal to 1 if
the state of Markov chain is m at time k, i.e. X_k=m, and 0
otherwise. The number of visits of node m, denoted by ν_m, can
be written in terms of the indicator function: ν_m=∑_k=0^∞1_{X_k=m}. The stopping criteria is hitting target node t for
the first time. In an irreducible chain, this event is guaranteed to
occur in a finite time. Hence k<∞. F_sm is defined as the
expected value of ν_m starting from s.


    F_sm   =   𝔼_s(ν_m)=𝔼_s ∑_k=0^<∞1_{X_k=m} = ∑_k=0^<∞𝔼_s(1_{X_k=m}) 
       =   ∑_k=0^<∞ℙ(X_k=m|X_0=s,X_<k≠ t) = ∑_k=0^<∞[P^k_11]_sm,

where the expression  is simply the expanded version of the matrix form. 
Note that in order for  F_sm to be finite (namely, the infinite
summation converges), it is sufficient that node t be reachable from
all other nodes in network. In other words, the irreducibility of the entire network is not necessary.




 §.§ Fundamental Tensor

We define the fundamental tensor,
F,  as a generalization of the fundamental matrix
F^{t}, which looks to be formed by stacking up the fundamental matrices constructed for
each node t as the target node in a strongly connected network (Eq.(<ref>)), but is in fact computed much more efficiently. In Theorem (<ref>), we show that the whole fundamental tensor can be computed from Moore-Penrose pseudo-inverse of Laplacian matrix with only O(n^3) of complexity and there is no need to compute the fundamental matrices for every target node which require O(n^4) of computation in total.

    F_smt=
    
    F^{t}_sm   if  s,m≠ t 
    
    0     if  s=t  or  m=t

Fundamental tensor is presented in three dimensions of source node, medial (middle) node, and target node (Fig. (<ref>)).



 §.§ Hitting Time


The (expected) hitting time metric, also known as the first
transit time, first passage time, and expected absorption time in the
literature, counts the expected number of steps (or time) required to
hit a target node for the first time when the random walk starts from
a source node. Hitting time is frequently used in the literature 
as a form of (random walk) distance metric for network analysis.  We
formally present it in three different forms below.



  * Matrix form <cit.>:
Hitting time can be computed from the fundamental matrix (<ref>) as follows:  

    h^{t}=F^{t}1,

where 1 is a vector of all ones and h^{t} is a vector of H_s^{t} computed for all s ∈𝒱∖{t}. H_s^{t} represents the expected number of steps required to hit node t starting from s and is obtained from: H_s^{t}=∑_m F^{t}_sm. The intuition behind this formulation is that enumerating the average number of nodes visited on the way from the source node to the target node yields the number of steps (distance) required to reach to the target node. 




  * Recursive form <cit.>:
The recursive form of H_s^{t} is the most well-known form presented in the literature for deriving the hitting time:

    H_s^{t}=1+∑_m∈𝒩_out(s)p_smH_m^{t}

It is easy to see the direct connection between the recursive form and
the matrix form: from
h=1+P_11h, we have 
h=(I-P_11)^-11.


  * Stochastic form <cit.>:
Let G=(X_k)_k>0 be a discrete-time Markov chain with the transition probability matrix P. The hitting time of the target node t is denoted by a random variable κ_t:Ω→{0,1,2,...}∪{∞}
given by
κ_t=inf{κ≥ 0: X_κ=t},
where by convention the infimum of the empty set ∅ is
∞. Assuming that the target node t is reachable from all the
other nodes in the network,  we have κ_t <∞. The
(expected) hitting time from s to t is then given by
 


    H_s^{t}   =   𝔼_s[κ_t]=∑_k=1^<∞ kℙ(κ_t=k|X_0=s)+∞ℙ(κ_t=∞|X_0=s) 
       =   ∑_k=1^<∞ kℙ(X_k=t|X_0=s,X_<k≠ t) 
       =   ∑_k=1^<∞ k∑_m≠ tℙ(X_k-1=m|X_0=s,X_<k-1≠ t)·ℙ(X_k=t|X_k-1=m) 
       =   ∑_k=1^<∞ k∑_m≠ t[P^k-1_11]_sm[p_12]_m,

where [P_11^0]_sm=1 for m=s and it is 0 otherwise. The
connection between the stochastic form and the matrix form can be
found in the appendix.









  §.§.§ Commute Time


The commute time between node i and node j is defined as the sum
of the  hitting time from i to j and the hitting time from j to i:

    C_ij=H_i^{j}+H_j^{i}

Clearly, commute time is a symmetric quantity,
i.e., C_ij=C_ji. In contrast,  hitting time is in general not
symmetric, even when   the network is undirected. 



 §.§ Hitting Cost

The (expected) hitting cost, also known as average first-passage
cost in the literature, generalizes the (expected) hitting time by
assigning a cost to each transition. Hitting cost from s to t, denoted by _s^{t}, is
the average cost incurred by the random walk starting
from node s to hit node t for the first time. The cost of
transiting edge e_ij is given by w_ij. The hitting cost was
first introduced by Fouss et al. <cit.> and given in
a recursive form. In the following, we first provide a rigorous definition for hitting cost
in the stochastic form, and then show how the matrix form and recursive form can be driven from this definition. 


	
	
  * Stochastic form:
	Let G=(X_k)_k>0 be a discrete-time Markov chain with the
        transition probability matrix P and cost matrix W.	The
        hitting cost of the target node t is a random variable η_t:Ω→𝒞 which is defined by
	η_t=inf{η≥ 0: ∃ k, X_k=t, ∑_i=1^k
          w_X_i-1X_i=η}. 𝒞 is a countable set. 
  If we view w_ij as the length of edge (link) e_ij, then the
  hitting cost η_t is the total length of steps that the random
  walk takes until it hits t for the first time.  The expected value
  of η_t when the random walk starts at node s is given by
	
    _s^{t}=𝔼_s[η_t]=∑_l∈𝒞 lℙ(η_t=l|X_0=s)

	
	For compactness, we delegate the more detailed derivation of the stochastic form and its connection
        with the matrix form to the appendix.
		



  * Matrix form:
	Hitting cost can be computed from the following closed form formulation:
	
    ^{t}=F r,

	where r is the vector of expected outgoing costs and ^{t} is a vector of _s^{t} computed for all s ∈𝒱∖{t}. The expected outgoing cost of node s is obtained from: r_s=∑_m∈𝒩_out(s) p_smw_sm. Note
	that the hitting time matrix H in Eq.(<ref>) is a
        special case of the hitting cost matrix , obtained when w_ij=1 for all e_ij.
	
	
	
	
	
  * Recursive form <cit.>:
	The recursive computation of _s^{t} is given as follows:
	
    _s^{t}=r_s + ∑_m∈𝒩_out(s)p_sm_m^{t}.
	
	It is easy to see the direct connection between the recursive
        form and the matrix form: from =r+P_11,
        we have =(I-P_11)^-1r.






  §.§.§ Commute Cost

Commute cost _ij is defined as the expected cost required to hit
j for the first time and get back to i. As in the case of commute
time, commute cost is a symmetric metric and is given by

    _ij=_i^{j}+_j^{i}
 



 §.§ Absorption Probability


The absorption probability, also known as hitting probability in the
literature, is the probability of hitting or getting absorbed by a
target node (or  any node in a set of  target nodes) in a finite time <cit.>. For a
single target node, this probability is trivially equal to 1 for all
nodes in a strongly connected network. We therefore consider  more
than one target nodes in this paper.   

Let indexes n-1 and n be assigned to two target nodes in a
strongly connected network. We partition the transition probability
matrix P as follows:









































    P=cccc    n-1     n    
    [ccc]c
    P_11   p_12   p_13   
    p'_21    p_n-1,n-1    p_n-1,n    n-1
    p'_31    p_n,n-1    p_n,n    n
 
where P_11 is an (n-2)×(n-2) matrix, p_12, p_13, p_21, and p_31 are (n-2)×1 vectors, and the rest are scalars.
The corresponding absorption probability can be expressed in three
forms as follows:

	
  * Matrix form <cit.>: The absorption probability matrix denoted by Q is a (n-2)× 2 matrix whose columns represent the absorption probabilities to target n-1 and n respectively:
	
	
    Q^{n-1,n}   =   Fp_12,
    	
    Q^{n-1,n}   =   Fp_13,

	where F=(I-P_11)^-1. The notation
        Q^{n-1,n} emphasizes that target n-1 is hit
        sooner than target n, and Q^{n-1,n}
        indicates hitting target n occurs sooner than target
        n-1. The formulation above states that to obtain the
        probability of getting absorbed (hit) by a given target when
        starting a random walk from a source node, we
        add up the absorption probabilities of starting from the
        neighbors of the source node, weighted by the number of times
        we expect to be in those neighboring nodes <cit.>. For a
        strongly connected network, these two probabilities are sum up
        to 1 for each starting node s, i.e., Q^{n-1,n}_s+Q^{n-1,n}_s=1. 
	
	
  * Recursive form <cit.>: For each of the target nodes, the absorption probability starting from any source node can be found from the absorption probabilities starting from its neighbors:
	
    Q^{n-1,n}_s   =   ∑_m∈𝒩_out(s)p_smQ^{n-1,n}_m,
    	
    Q^{n-1,n}_s   =   ∑_m∈𝒩_out(s)p_smQ^{n-1,n}_m,

	where s,m ∈𝒱∖{n-1,n}.
	Note that the neighbors of a node can also be the target
        nodes. Thus, the right-hand side of the above equations is
        decomposed into two parts: Q^{n-1,n}_s= p_sn
        + ∑_m≠ n,n-1p_smQ^{n-1,n}_m, and the
        same way for Q^{n-1,n}_s. Now, it is easy to
        see how the recursive form is connected to the matrix form:
        from
        Q^{n-1,n}=p_13+P_11Q^{n-1,n},
        we have 
Q^{n-1,n}=(I-P_11)^-1p_13.
	 
	
  * Stochastic form <cit.>:
	Let G=(X_k)_k>0 be a discrete-time Markov chain with the
        transition matrix P. The hitting time of the target state n before n-1 is denoted by a random variable κ_n:Ω→{0,1,2,...}∪{∞}
	given by
	κ_n=inf{κ≥ 0: X_κ=n,
          X_k<κ≠ n,n-1}. Then the probability of ever
        hitting n is ℙ(κ_n<∞)
        <cit.>. This can be derived as follows:
	
    Q^{n-1,n}_s    =   ∑_k=1^<∞ℙ(κ_n=k|X_0=s) 
       =   ∑_k=1^<∞ℙ(X_k=n|X_0=s,X_<k≠ n,n-1) 
       =   ∑_k=1^<∞∑_m≠ n, n-1ℙ(X_k-1=m|X_0=s,X_<k-1≠ n,n-1)·
          ℙ(X_k=n|X_k-1=m) 
       =   ∑_k=1^<∞∑_m[P^k-1_11]_sm[p_13]_m
       =   ∑_m[(I-P_11)^-1]_sm[p_13]_m.

The stochastic form for Q^{n-1,n}_s is derived in a
similar vein.










 §.§ Generalization: Markov Metrics for a Set of Targets
 

Let 𝒜={t_1,...,t_|𝒜|} be a set of target nodes. Then the transition probability matrix can be written in the following form:

    P=[
    [ P_𝒯𝒯 P_𝒯𝒜; P_𝒜𝒯 P_𝒜𝒜 ]],

where 𝒯=𝒱∖𝒜 is the set of
non-target nodes. Note that set of target nodes
𝒜 can  be modeled as the set of absorbing states in a
Markov chain, and then 𝒯=𝒱∖𝒜 is the set of
transient (non-absorbing) nodes. Since hitting the target nodes is the stopping criterion
for all the Markov metrics we have reviewed so far,  it does not
matter where the random walk can go afterwards and what the outgoing
edges of the target nodes are. Therefore, there is no difference
between P=[ 
[ P_𝒯𝒯 P_𝒯𝒜; P_𝒜𝒯 P_𝒜𝒜 ]] and P=[
[ P_𝒯𝒯 P_𝒯𝒜;    0    I ]] for computing the Markov metrics. 


For a given set of target nodes 𝒜, the fundamental matrix
F^𝒜 is obtained using the following relation: 

    F^𝒜=I+∑_k=1^<∞ P^k_𝒯𝒯=(I-P_𝒯𝒯)^-1,

which is a  general form of the fundamental matrix defined for a
single target (Eq.(<ref>)). Entry F^𝒜_sm
represents the expected number of visits to m before hitting
any of the target nodes in 𝒜 when starting a
random walk from s. 

A hitting time for 𝒜 is defined as the expected number of
steps to hit the set for the first time which can occur by hitting
any of the target nodes in this set. The vector of hitting
times with respect to a target set 𝒯 can be computed
using 

    h^𝒜=F^𝒜1


If there exists a matrix of costs W defined for the network, the
hitting cost for target set 𝒜 is given below

    ^𝒜=F^𝒜r,

where r is a vector of expected outgoing cost r_s's: r_s=∑_m∈𝒩_out(s) p_smw_sm.

The absorption probability of target set 𝒜 is a |𝒯|×|𝒜| matrix whose columns represents the absorption probability for each target node if it gets hit sooner than the other target nodes:

    Q^𝒜=F^𝒜P_𝒯𝒜,

where Q^𝒜 is a row-stochastic matrix for a strongly connected network.

We remark that if the network is not strongly connected (thus the
corresponding Markov chain is not irreducible), I-P_𝒯𝒯
may not be  non-singular for every set of 𝒜. Hence
F^𝒜 may not exist. The necessary and sufficient
condition for the existence of F^𝒜 is that target set 𝒜 includes at
least one node from each recurrent equivalence class in the
network. The recurrent equivalence
class is the minimal set of nodes that have no outgoing
edge to nodes outside the set. Once a random walk reaches a node in 
a recurrent equivalence class, it can no longer get out of that set. A recurrent equivalence class can be as small as
one single node, which is called an absorbing node.






§ USEFUL RELATIONS FOR MARKOV METRICS
 
In this section, we first establish several important theorems, and then
gather and derive a number of useful relations among the Markov
metrics. We start by relating the fundamental tensor with the Laplacian
matrices of a general network. For an undirected network or graph G, the
graph Laplacian L^u=D-A (where A is the adjacent matrix of G and
D=diag[d_i] is the diagonal matrix of node degrees) and its normalized
version  L̃^u=D^-1/2LD^-1/2 have been
widely studied and found many applications (see, e.g., <cit.> and the references therein). In particular, it is
well-known that  commute times are closely related to the
Penrose-Moore pseudo-inverse of L^u (and a variant of Eq.(<ref>)
also holds for L̃^u):
	
    C_ij=L^u,+_ii+L^u,+_jj -L^u,+_ij-L^u,+_ji.


Li and Zhang <cit.> were first to
introduce the (correct) generalization of graph Laplacians for directed
networks/graphs (digraphs) using the stationary distribution 
{π_i} of the transition matrix P=D^-1A for the associated (random walk)
Markov chain defined on a directed network G. For a strongly
connected network G, its  normalized digraph Laplacian is
defined as L̃ =Π^1/2 (I-P) Π^-1/2, where Π=diag[π_i] is the diagonal
matrix of stationary probabilities. Li and Zhang proved that
the hitting time and commute time can be computed from the Moore-Penrose pseudo-inverse L̃^+ of L̃ using the following relations:
	
    H_i^{j}=L̃^+_jj/π_j - L̃^+_ij/√(π_iπ_j)

and 
	
    C_ij=H_i^{j}+ H_j^{i}=L̃^+_ii/π_i+L̃^+_jj/π_j - L̃^+_ij/√(π_iπ_j) -L̃^+_ji/√(π_iπ_j).


We define the (unnormalized) digraph Laplacian for a general
(directed or undirected) network G as L=Π(I-P) and the random walk Laplacian as L^p=I-P. Clearly, L̃
=Π^-1/2 L Π^-1/2 =Π^1/2
L^pΠ^-1/2.  Note that for a (connected) undirected
graph, as π_i=d_i/vol(G) where vol(G)=∑_j d_j, we see that
the classical graph Laplacian L^u=D-A =  vol(G)L. Any results which hold
for L also hold for L^u=D-A with a scalar multiple. In the following we relate
the fundamental tensor to the digraph and random walk Laplacians L
and L^p, and use this relation to establish similar expressions for
computing hitting and commute times using L, analogous to
Eqs.(<ref>) and (<ref>).

 
	Let [
	[  L_11  l_12; l'_21  l_nn ]] be an n × n irreducible matrix
      such that nullity(L)=1. Let M=L^+ be the Moore-Penrose pseudo-inverse of L
      partitioned similarly and (𝐮',1)L=0, L(𝐯;1)=0, where
      𝐮 and 𝐯 are (n-1)-dim column vectors, 𝐮' is
      the transpose of the column vector 𝐮
      ((𝐮',1) is a n-dim row vector and (𝐯;1)
      is a n-dim column vector, a la MATLAB). Then the inverse of the (n-1) × (n-1) matrix L_11 exists and is given by:
	
    L_11^-1=(I+𝐯𝐯')M_11(I+𝐮𝐮'),

	where I denotes the (n-1)× (n-1) identity matrix.

Note that node n in the above lemma can be substituted by any other node (index).  

 
	The fundamental tensor can be computed from the Moore-Penrose
        pseudo-inverse of the digraph Laplacian matrix
        L=Π(I-P) as well as the  random
          walk Laplacian matrix
        L^p=I-P as follows, which results to O(n^3) time complexity:
	
    F_smt=(L_sm^+ - L_tm^+ + L_tt^+ - L_st^+)π_m,

	
    F_smt=L^p_sm^+ - L^p_tm^+ + π_m/π_tL^p_tt^+ - π_m/π_tL^p_st^+,

	where π_i is the stationary probability of node i and Π is a diagonal matrix whose i-th diagonal entry is equal to π_i.
 

 Note that F=(I-P_11)^-1=L_11^-1 as in
 Lemma <ref>.  The above equations follow from
 Lemma <ref> with v=u=1.
 The nullity of matrix L^p=I-P for a strongly connected network
 is 1. Using Eq.(<ref>) or (<ref>), all n^3 entries of the fundamental tensor F can be computed from L^+ in constant time each.






  
	
    ∑_s,tF_smt=cπ_m,

	where c is a constant independent of m.


	
    ∑_s,tF_smt   =   ∑_s,t (L_sm^+ - L_tm^+ - L_st^+ + L_tt^+)π_m  
    	
       =    0 - 0 - 0 + (n ∑_t L_tt^+)π_m
    	
       =    cπ_m,

	where the second equality follows from the fact that the
        column sum of L^+=(Π(I-P))^+ is zero. Later in
        Section <ref>, we will show that
        c=|ℰ|K, where K is the Kirchhoff index of a
        network. 



	Hitting time and commute time can also be expressed in terms
        of entries in the digraph Laplacian matrix L=Π(I-P) <cit.>:
	
    H_i^{j}=∑_m (L_im^+ - L_jm^+)π_m + L_jj^+ - L_ij^+,

	
    C_ij=L_ii^+ + L_jj^+ - L_ij^+ - L_ji^+,



	Use Eq.(<ref>) and (<ref>).

Note that we can also write the metrics in terms of the random walk Laplacian matrix L^p by a simple substitution: L_im^+ - L_ij^+ = L^p_im^+/π_m - L^p_ij^+/π_j.


	Hitting cost  and commute cost  can be expressed  in terms of the digraph Laplacian matrix L=Π(I-P):
	
    _ij=∑_m (L_im^+ - L_jm^+ + L_jj^+ - L_ij^+)g_m,

	
    _ij=(L_im^+ - L_jm^+ + L_jj^+ - L_ij^+)∑_m g_m,

	where g_m=r_m π_m and r_m=∑_k∈𝒩_out(m) p_mkw_mk.


	Use Eq.(<ref>) and (<ref>). From Eq.(<ref>)
        and (<ref>), it is also interesting to note that commute cost is a multiple scalar of commute time.


 
	Let C be an n× n non-singular matrix and suppose A=C-uv' is singular. Then the Moore-Penrose pseudo-inverse of A is given as:
	
    A^+=(I-xx'/x'x)C^-1(I-yy'/y'y),

	where x=C^-1u, y'=v'C^-1.


 
	For an ergodic Markov chain, the Moore-Penrose pseudo-inverse of random-walk Laplacian L^p^+ can be computed from fundamental matrix Z=(I-P+1π')^-1 <cit.> as follows:
	
    L^p^+=(I-Z11'Z'/1'Z'Z1)Z(I-Z'ππ'Z/π'ZZ'π),

	where 1 is a vector of all 1's and π denotes the vector of stationary probabilities.


	The theorem is a direct result of applying Lemma <ref>.

Theorem <ref> along with Theorem <ref> reveal the relation between the fundamental matrices F and Z. They also show that the fundamental tensor F can be computed by a single matrix inverse, can it be either a Moore-Penrose pseudo-inverse or a regular matrix inverse, as L^p^+ in Eq. (<ref>) can be computed by either operating the pseudo-inverse on L^p or using Eq. (<ref>). 
Discussion on computing Markov metrics via the group inverse can be found in <cit.>.
 
 
	The fundamental matrix for  target set  𝒮_1∪𝒮_2 can be computed from the fundamental matrix for
        target set 𝒮_1 as follows,
	
    F^𝒮_1∪𝒮_2_im=F^𝒮_1_im-F^𝒮_1_i𝒮_2[F^𝒮_1_𝒮_2𝒮_2]^-1F^𝒮_1_𝒮_2m,

	where  F^𝒮_1_i𝒮_2 denotes the row
        corresponding to node i and the columns corresponding to set
        𝒮_2 of the fundamental matrix F^𝒮_1,
        and the (sub-)matrices
        F^𝒮_1_𝒮_2𝒮_2 and
        F^𝒮_1_𝒮_2m are similarly defined.






	Consider the  matrix M=I-P_𝒯𝒯,  where the
        absorbing set is 𝒜=𝒮_1 and the transient
        set 𝒯=V∖𝒮_1. The inverse of M
        yields the fundamental matrix F^𝒮_1, and the
        inverse of its sub-matrix obtained from removing rows and
        columns corresponding to set 𝒮_2 yields the
        fundamental matrix F^𝒮_1∪𝒮_2. Using the
        following equations from the Schur complement,  we see that the inverse of  a
        sub-matrix can be derived 
        from that of the original matrix.
	
 If A is invertible, we can factor the matrix M=[
	[ A B; C D ]] as follows
	
    [
    	[ A B; C D ]] =
    	[
    	[     I     0; CA^-1     I ]]
    	[
    	[        A        B;        0 D-CA^-1B ]]

	Inverting both sides of the equation yields
	
    [
    	[ A B; C D ]]^-1   =   [
    	[       A^-1 -A^-1BS^-1;          0       S^-1 ]]
    	[
    	[      I      0; -CA^-1      I ]]
    	
       =   [
    	[ A^-1+A^-1BS^-1CA^-1          -A^-1BS^-1;          -S^-1CA^-1                S^-1 ]]
    	
       =   [
    	[ X Y; Z W ]],

	where S=D-CA^-1B. Therefore, A^-1 can be computed from A^-1=X-YW^-1Z.



	The simplified form of Theorem <ref> for a single
        target is given by
	
    F^{j,k}_im=F^{j}_im-F^{j}_ikF^{j}_k,m/F^{j}_k,k



 
	
    P_𝒯𝒯F^𝒜=F^𝒜P_𝒯𝒯=F^𝒜,

	where 𝒯∪𝒜=𝒱


	It follows easily from Eq.(<ref>).



	
    F^{j}_im=
    	∑_k∈𝒩_in(m) F^{j}_ikp_km   if  i≠ m 
    
    	1+∑_k∈𝒩_in(m) F^{j}_ikp_km   if  i= m
	  


	It is a special case of Lemma <ref>. Note that
        the recursive relation in Eq.(<ref>) is  in terms of s's outgoing neighbors, while this one is in terms of incoming neighbors of m.
 

 
	The absorption probability of a target node j in an
        absorbing set 𝒜={j}∪𝒮 can be
        written in terms of the normalized fundamental matrix
        F^𝒮,  where the columns are normalized by the diagonal entries:
	
    Q^𝒜_ij=F^𝒮_ij/F^𝒮_jj



	
    Q^𝒜_ij   =   [F^𝒜P_𝒯𝒜]_ij
       =   ∑_m∈𝒯 F^𝒜_imp_mj
       =   ∑_m∈𝒯 (F^𝒮_im-F^𝒮_ij F^𝒮_jm/F^𝒮_jj)p_mj
       =   ∑_m∈𝒯 F^𝒮_imp_mj-F^𝒮_ij/F^𝒮_jj∑_m∈𝒯 F^𝒮_jmp_mj
       =   F^𝒮_ij-F^𝒮_ij/F^𝒮_jj(F^𝒮_jj-1) 
       =   F^𝒮_ij/F^𝒮_jj,

	where the third and fifth equalities follow directly from of Theorem <ref> and Lemma <ref>, respectively.



We are now in a position to gather and derive a number of useful relations among the random walk
metrics. 


[Complementary relation of absorption probabilities]
	
    Q^𝒜_ij=1-∑_k∈𝒜∖{j} Q^𝒜_ik,

	where i ∈𝒯 and j ∈𝒜.


	Based on the definition of Q and the assumption that all the
        nodes in 𝒯 are transient, the probability that a random walk eventually ends up in set 𝒜 is 1.


[Relations between the fundamental matrix and commute time]
	
    (1)    F_ii^{j}=π_i C_ij
       (2)   F_im^{j}/π_m+F_mi^{j}/π_i=C_ij+C_jm-C_im
       (3)   F_im^{j}/π_m+F_ij^{m}/π_j=C_jm
       (4)    F_im^{j}+F_jm^{i}=π_m C_ij



	Use (<ref>) and (<ref>).
 


[The hitting time detour overhead in terms of other metrics]
	
    (1)    H_i^{j}+H_j^{m}-H_i^{m}=F_im^{j}/π_m
       (2)    H_i^{j}+H_j^{m}-H_i^{m}= Q_i^{m,j}C_mj



	For the first equation use (<ref>) and (<ref>), and for the second one use the previous equation along with (<ref>) and (<ref>).


[The hitting time for two target nodes in terms of
  hitting time for a single target]
	
    H_i^{j,k}=H_i^{k}-Q_i^{j,k}H_j^{k}=H_i^{j}-Q_i^{k,j}H_k^{j},

	which can also be reformulated as: H_i^{j}=H_i^{j,k}+Q_i^{k,j}H_k^{j}.


	Aggregate two sides of Eq.(<ref>) over m and
        substitute Eq.(<ref>) in it.


[Inequalities for hitting time]
	
    (1)    H_i^{m}+H_m^{j}≥ H_i^{j}    (triangular inequality)
       (2)    H_i^{j}≥ H_i^{j,m}
       (3)    H_i^{m}+H_m^{j,k}≥ H_i^{j,k}

 

	For the first inequality, use (<ref>) and (<ref>).
	For the second inequality,  use the aggregated form of
        Eq.(<ref>) over m and the fact that the entries of
        F  are  non-negative. The third inequality  is a
        generalization of the first one.


[Inequalities for the fundamental matrix]
	
    (1)    F_im^{j}F_kk^{j}≥ F_ik^{j}F_km^{j}
       (2)    F_kk^{j}≥ F_ik^{j}



	For the first inequality,  use Eq.(<ref>) and the
        fact that F is non-negative. The second one can be derived
        from Eqs.(<ref>), (<ref>) and (<ref>). Note
        that these two inequalities hold for any absorbing set
        𝒜, hence we drop the superscripts. 


[Inequality for absorption probabilities]
	
    Q_i^{m,j}≥ Q_i^{k,j}Q_k^{m,j}



	Use (<ref>) and (<ref>).


[Inequality for the digraph Laplacian matrix]
	
    L_im^++L_kk^+≥ L_ik^++ L_km^+



	Use (<ref>) and the fact that F's entries are always non-negative.
 

[Relations for undirected networks (reversible Markov chain)]
	
    (1)   F_im^{S}/π_m=F_mi^{S}/π_i
       (2)   Q_i^{m,j}C_m^{j}= Q_m^{i,j}C_i^{j}
       (3)   H_i^{m}+H_m^{j}+H_j^{i}=H_m^{i}+H_j^{m}+H_i^{j}



	The first equation follows from Eq.(<ref>) and the fact
        that L^+ is symmetric for undirected networks.
	The second equation can be derived by using Eqs.
        (<ref>), (<ref>), (<ref>) and  the fact that L^+ is symmetric.
	The third equation follows from Eq.(<ref>) and  L^+ being symmetric.





















































































§ UNIFYING RANDOM-WALK DISTANCE, CENTRALITY, AND TOPOLOGICAL MEASURES
 

Many network measures have been proposed in the literature for network
analysis purposes <cit.>, such as distance metrics for measuring the similarity (or diversity) between nodes or
entities of a network, centrality measures to assess a node's involvement or importance
in the connectivity or communication between network entities, and
topological indices to measure the structural stability of
networks. In this section, we review some of these network measures
proposed in the literature, and show that these measures can be
unified in terms of the fundamental tensor, which  provides a
coherent framework for computing them and understanding the relations
among them. 

	Fundamental tensor F unifies various network
        random-walk measures via summation along one or more dimensions shown in Figure <ref>.





 §.§ Random-walk distance measure

The hitting time metric has been used extensively in different
application domains, such as a distance (or dissimilarity) measure for clustering and
classification purposes <cit.>. Note that this
distance metric satisfies two out of three conditions for the general
distance metric: It is positive when two ends are different and zero
when two ends are identical. As noted earlier, the hitting time metric
is in general not symmetric, but it satisfies the triangle inequality.
In Section <ref>, we have shown that hitting time can
be computed from the fundamental tensor by summing over m's (the
middle node dimension, see Figure <ref>).

    Distance_rw(s,t) = H_s^{t}=∑_m F_smt.

With a cost matrix W, the hitting cost distance (<ref>) is
obtained by the weighted sum over the medial node dimension of the fundamental tensor: _s^{t}= ∑_m F_smt b_m,
where b_m = ∑_i w_mip_mi is the expected outgoing cost of node m.  



 §.§ Random-walk centrality measures

Network centrality measures can be  broadly categorized into two main types <cit.>: i)
distance-based and ii) volume-based. The closeness centrality is an
example of the  distance-based measures, whereas the  betweenness centrality is an example of volume-based measures. 

	
  * Random-walk closeness measure:  Closeness centrality
          ranks nodes in a network  based on their total distance from
          other nodes of the network. This measure reflects how
          easily/closely the node is accessible/reachable from the
          other parts of the network,  and in a nutshell how
          “central” the node  is located within a network. The classical
          closeness centrality metric is defined using the shortest
          path distances.  Noh and
          Rieger <cit.> introduces the random walk
            closeness centrality, which is  defined using the hitting
          time distance: A node is considered to have a high
          centrality value if and only if  its total hitting time distances
          from other nodes in the network is small. This closeness
          centrality measure  can be easily expressed in terms of the random walk fundamental tensor:
	
    Closeness_rw(t)=∑_s H_s^{t}=∑_s,mF_smt,

	or in the reciprocal form to imply lower importance with small closeness value: Closeness_rw(t)=|𝒱|/∑_s,mF_smt.
	
	
  * Random-walk betweenness measure: Betweenness measure
          quantifies the number of times a node acts as a “bridge”
          along the paths between different parts of the network. 
          The larger the number of paths crossing that node, the more
          central the node is. As a special case, the node degree, deg(m), can
          be viewed as a betweenness centrality measure in an
          undirected network. Clearly, it captures how many paths of
          length 1 going through node m (or many 1-hop neighbors it
          has) <cit.>. It is also proportional to
          the total number of (random) walks passing through node m
          from any source to any target in the network. This follows
          from the following more general statement. For a general
          (strongly connected)  network, we define the
          random walk betweenness of node m as follows and
          show that it is proportional to π_m, the stationary
          probability of node m:
	
    Betweenness_rw(m)    =   ∑_s,tF_smt
       =   ∑_s,t (L_sm^+ - L_tm^+ - L_st^+ + L_tt^+)π_m  
    	
       =    |𝒱| ∑_t L_tt^+π_m
    	
       =    |ℰ| Kπ_m,
 
	where K is the Kirchhoff index (see
        Section <ref>). The third equality follows by
        using the fact that  the column sum of the digraph Laplacian
        matrix L^+=(Π(I-P))^+ is zero
        <cit.>. For a (connected)
        undirected network, π_m=d_m/2|ℰ|, where d_m is the
        degree of node m. 

		
	For undirected networks, Newman <cit.> proposes  a variation of the random
        walk betweenness measure defined above, which we denote by
        Betweenness_Newman,bidirect(m) (the use of
        subscript bidirect will be clear below): it is defined
        as the (net) electrical  current flow I through a medial
        node in an undirected network (which can be viewed as an
        electrical resistive network with bi-directional links with
        resistance),  when a unit current flow is injected at a source
        and removes at a target (ground), aggregated over all such
        source-target pairs. Formally, we have 
	
    Betweenness_Newman,bidirect(m)    =   ∑_s,t I(s→ m→ t) 
       =   ∑_s,t∑_k 1/2|F_smt p_mk - F_skt p_km|.

We remark that the original definition given by Newman is based on
current flows in electrical networks, and is only valid for undirected networks. Define f(F_smt) = ∑_k
1/2|F_smt p_mk - F_skt
p_km|, then 
Betweenness_Newman,directed(m)=∑_s,tf(F_smt)
yields a general definition of Newman's random walk betweenness measure that also
holds for directed networks. In particular, we show that if a network
is strictly unidirectional, namely, if e_ij∈ E then
e_ji∉ E, Newman's random walk betweenness centrality reduces
to Betweenness_rw(m)=|ℰ| Kπ_m: 
	
    Betweenness_Newman,unidirect(m)    =   ∑_s,t∑_k |F_smt p_mk| 
       =   ∑_s,tF_smt∑_k p_mk
       =   ∑_s,tF_smt = |ℰ| Kπ_m,

	where K is the Kirchhoff index (see
        Section <ref>) and the last equality follows
        from Corollary <ref>. 










 §.§ Kirchhoff Index

The term topological index is a single metric that characterizes
the topology (“connectivity structure”) of a network; it has been
widely used in mathematical chemistry to reflect certain structural
properties  of the underlying molecular graph
<cit.><cit.>.
Perhaps the most known topology index is the Kirchhoff
index <cit.> which has found a variety of
applications <cit.>. Kirchhoff index is also closely connected to Kemeney's constant <cit.>. 
The Kirchhoff index is often defined in terms of effective
  resistances <cit.>, K(G)=1/2∑_s,tΩ_st, which is closely related to commute times, as
Ω_st=1/|ℰ|C_st <cit.>.
Hence we have 

    K(G)=1/2|ℰ|∑_s,t C_st= |𝒱|/|ℰ|∑_t L_tt^+=1/|ℰ|∑_s,m,tF_smt,

where the second equality comes  from Eq.(<ref>). 
In other words, the Kirchhoff index can be computed by summing over
all three dimensions in Figure <ref>, normalized by the
total number of edges. 

The relations between Kirchhoff index, effective resistance, and Laplacian matrix have been well studied in the literature.
 The authors
in <cit.> provided three interpretations of
L^+_ii as a topological centrality measure, from effective resistances in an electric network, random
walk detour costs, and graph-theoretical topological connectivity
via connected bi-partitions, and demonstrate that the Kirchhoff index, as a
topological index, captures the overall robustness of a network.
 The relation between the effective resistance and the Moore-Penrose inverse of the Laplacian matrix is more elaborated in <cit.>, and insightful relations between Kirchhoff index and inverses of the Laplacian eigenvectors can be found in <cit.>.



§ CHARACTERIZATION OF NETWORK ARTICULATION POINTS AND NETWORK LOAD DISTRIBUTION

We extend the definition of articulation point to a general (undirected and directed) network as a node whose
removal reduces the amount of reachability in the network. For
instance, in a network G, if t is previously reachable
from s, i.e. there was at least one path from s to t, but t is no longer reachable
from s after removing m, node m is an
articulation point for network G. Note that s may still be reachable from t after removing m in a directed network, which is not the case for an undirected network. Hence, in an undirected network, the reduction in the number of reachabilities results to the increase in the number of connected components in the network, which is the reason to call articulation point as cut vertex in the undirected networks. Removal of an articulation point in a directed network,
however, does not necessarily increase the number of connected components in the
network. 

As an application of the fundamental tensor, we introduce  the normalized fundamental tensor
F̂ and show that its entries contain information
regarding articulation points in a general (directed or undirected)
network.  If F_smt exists, its normalized
version is defined as follow,

    F̂_smt=F_smt/F_mmt   if  s,m≠ t 
    
    0     if  s=t  or  m=t

The normalized fundamental tensor satisfies the following properties: a)
0≤F̂(s,m,t) ≤ 1, and b)
F̂_smt = Q_s^{m,t}.
Recall that Q_s^{m,t} is the absorption probability
that a random walk starting from node s hits (is absorbed by) node
m sooner than node t.  The second property (b) is a result of  Theorem <ref>  and the
first property (a) follows from (b). Clearly,
F̂_smt =Q_s^{m,t}=1 means that
with probability 1, any random walk starts from node s always hit
node m before node t. Hence node m is on any path (thus walk)
from s to t. Hence it is an articulation point. We therefore have
the following statement:

The normalized fundamental tensor captures the articulation points of
a network: if F̂_smt=1, then node m is an
articulation point; namely, node m is located on all paths from s to t. On the other extreme, F̂_smt=0 indicates
that m is not located on any path from s to t and thus it plays no role for this reachability.  


Figure <ref> depicts  two simple networks, one
undirected and one directed, and displays the corresponding normalized
fundamental tensors we have computed for these two networks (the
tensors are “unfolded” as a series of matrices, each with fixed
t). Any column that contains an entry with value 1 indicates the
corresponding node m, 1 ≤ m ≤ 5, is located on all paths between a pair of source and target, and so is an articulation point
for the network [As a convention, the source node is considered as the articulation point of the reachability, but not the target.]. Counting the number of 1's in each column m over the
entire tensor yields the number of source-target pairs for which  node m is
an articulation point. The larger this count is, the more critical
node m is for the overall network reachability. For instance, for
both networks,  node 3 is the most critical node for network reachabilities. 



More generally, we can view F̂_smt as a measure
of how critical a role node m plays in the reachability from node
s to node t. As a generalization of articulation points, we define
the overall load that node m carries for all source-target
pairs in a network as follows:

    Load(m) = 1/(n-1)^2∑_s,tF̂_smt,


It is interesting to compare Eq.(<ref>) with
Eq.(<ref>), where the latter (the unnormalized 
summation  ∑_s,tF_smt) is proportional to the
stationary probability of node m (and degree of m if the network
is undirected). The distribution of Load(m)'s provides a
characterization of how balanced a network in terms of distributing its load
(reachability between pairs of nodes), or how robust it is against
targeted attacks. A network with a few high-valued articulation points
(e.g., a star network) is more vulnerable to the failure of a few
nodes. Using a few synthetic networks with specific topologies
as well as real-world networks as examples,  Figure <ref>
plots the distribution of Load(m) for these networks (sorted based
on increasing values of Load(m)'s).  Among the specific-shaped networks, it is interesting to note that
comparing to a chain network, the loads on a cycle network are evenly
distributed – this shows the huge difference that adding a single
edge can make in the structural property of a network. It is not
surprising that the complete graph has evenly distributed loads. 
In constrast, a star graph has the most skewed load distribution, with
the center node as an articulation point of the network. Comparing the
binary tree, the grid network has a less skewed load distribution. It
is also interesting to compare the load distribution of the binary
with that of  a  3-ary “fat tree” network – such a topology is used
widely in data center networks <cit.>. The real networks used
in Figure <ref>(b) include the Arxiv High Energy Physics
 - Phenomenology collaboration network (CAHepPh) <cit.>,
 a sampled network of Facebook <cit.>, the coauthorship
 network of network scientists (netSci) <cit.>, the Italian
 power grid <cit.>, and a protein-protein  interaction network <cit.>.
 For comparison, we also include three networks generated via two
 well-known random network models,  the Preferential Attachment generative model (PA)
 <cit.> and  Erdos Renyi (ER) random graph model <cit.> with two different initial links of 8
 (random) and 40 (random2). We see that the two ER random networks
 yield most balanced load distributions, whereas the PA network
 exhibits behavior similar to a tree network, with a few nodes bearing
 much higher loads than others. The real networks exhibit load
 distributions varying between these types of random networks (with
 the  Italian power grid closer to an ER random network, whereas
 netSci closer to a PA random network).




 



§ MOST INFLUENTIAL NODES IN SOCIAL NETWORKS
 
Online social networks have played a key role as a medium for the
spread of information, ideas, or “influence” among their
members. The Influence maximization problem in social networks is about finding the most
influential persons who can maximize the spread of influence in the
network. This problem has applications in viral marketing, where a
company may wish to spread the publicity, and eventually the adoption, of a new
product via the most influential persons in popular social networks. A
social network is modeled as a (directed or undirected) graph where nodes represent the
users, and edges represent relationships and interactions between the
users. An influence cascade over a network can be modeled by a
diffusion process, and the objective of the influence maximization
problem is to find the k most influential persons as the initial
adopters who will lead to most number of adoptions.  

The heat conduction model <cit.> is a diffusion
process which is inspired by how heat transfers through a medium from the part with higher temperature to the part with lower
temperature. In this diffusion process, the probability that a user 
adopts the new product is a linear function of adoption probabilities 
of her friends who have influence on her as well as her own
independent tendency. We modeled the independent tendency of users
for the product adoption by adding an exogenous node, indexed as o, and linked to all of the
nodes in the network. Network G with added node o is called
extended G, denoted by G^o. We showed that the influence
maximization problem for k=1, where k=# initialadopters,
under the heat conduction diffusion process has the following solution in
terms of the normalized fundamental tensor over G^o
<cit.>:    

    t^* = _t∑_s ∈𝒱F̂_sto.


We also proved that the general influence maximization problem for k>1 is NP-hard <cit.>. However, we proposed an
efficient greedy algorithm, called C2Greedy
<cit.>, which finds a set of
initial adopters who produce a provably near-optimal 
influence spread in the network. The algorithm iteratively finds the
most influential node using Eq.(<ref>), then removes it from the
network and solves the equation to find the next best initiator.  

 For k=1,  _t∑_s ∈𝒱F̂_sto
finds the most influential node of network G^o as the initial
adopter for maximizing the influence spread over the network with heat
conduction <cit.> as the diffusion process.
For k>1, the greedy algorithm,  C2Greedy <cit.>, employs this relation to
iteratively find the k most influential nodes, which yields a
provably near-optimal solution. 




In <cit.>, we showed that C2Greedy outperforms the state-of-the-art influence maximization algorithms in both performance and speed, which we do not repeat here. Instead, we present two new sets of experiments in the rest.
 
We remark that the metric in Eq.(<ref>) addresses both the
global characteristics of the network by placing the most
influential node in the critical and strategical “center” of the network,
and the local characteristics by specifying the highly populated
and “neighbor-rich” nodes. In Figure <ref>(a), we 
visualize the influence spread of
the two most influential nodes found from C2Greedy using the ESNet <cit.> network. The initiators are colored
in black, and the green shades indicate the
influence spread over the nodes in the network; the darker the green, the higher probability of production adoption for the node. In
Figure <ref>(b), we pick two nodes, which are a neighbor of the two
most influential nodes identified by C2Greedy, as the initiators, and
visualize the probability of influence spread caused by these two
nodes over other nodes in the network. The lower green intensity of
Figure <ref>(b), compared to that of Figure <ref>(a)
shows that not any two initiators – even if they are their immediate neighbors and globally located very closely – can cause the same influence spread
as the  two most influential nodes identified by C2Greedy.

Moreover, we show that the k most influential initiators found by C2Greedy have higher influence spread in the network compared to that of well-known centrality/importance measure algorithms: 1- top k nodes with highest
(in-)degree, 2- top k nodes with highest closeness centrality scores, 3- top k nodes with highest
Pagerank score <cit.>, and 4- a benchmark which consists of k nodes picked randomly. For this purpose, we use real-world network data from three social
networks, wiki vote <cit.>, hepPh citation <cit.>,
and Facebook <cit.>. Figure <ref> illustrates how the C2Greedy outperforms the other algorithms for a wide range of k.











§ FAST COMPUTATION OF DYNAMIC NETWORK REACHABILITY QUERIES

Reachability information between nodes in a network is crucial for a
wide range of applications  from gene interactions in bioinformatics
<cit.> to XML query processing
<cit.>. Given a network, a reachability query R(s,
t) has a binary answer with 1 indicating that target node t is
reachable from source node s, and 0 representing that it is
not.  Several efficient algorithms have been devised to answer reachability queries when the
network is static <cit.>.
However, few efficient solutions have been developed to answer
reachability query for dynamic networks, e.g., after node or
link failures. For example,  garbage collection in programming
languages requires dynamic (re-)computation of reachability  to balance the reclamation of memory, which might be
reallocated. The speed of answering reachability queries affect the performance of  applications <cit.>. 

As a final application of the fundamental tensor, we illustrate how it can
be employed to develop an efficient algorithm to answer reachability
queries for dynamic networks. Here we do not require the network G
under consideration (before or after failures) be strongly connected,
otherwise the reachability query problem is trivial. For simplicity of
exposition, in the following we only consider node failures. Similar in
Section <ref>, we add an exogenous node
o to network G and connecting all the nodes to it. We note that
this  extended network G^o has only one recurrent equivalence class,
and F_sto exists for any pairs of s and t.  Moreover,
 F_sto is non-zero if and only t is reachable from
 s in G. This is because with non-zero probability a random walk will  visit every node that is reachable
 from s  before hitting o. By pre-computing the fundamental matrix
 F^{o} once, we can answer any reachability query
 R(s,t) in constant time using F^{o} by  performing a table look-up.

Now suppose a set of nodes, ℱ, fail. We claim that we can
answer the dynamic reachability query R(s,t,ℱ) (after
the nodes in ℱ fail, but without prior knowledge of the
node failure set ℱ)  in O(|ℱ|). In particular,
if |ℱ| is of a constant order O(1) compared to the size
of network |𝒱|, then the queries are answered in constant O(1)
time.  This is achieved by leveraging Theorem <ref> for incremental computation of the
fundamental matrix. Let 
 𝒮=ℱ∪{o} and define F_st𝒮

    F_st𝒮=F_sto-F_sℱoF^-1_ℱℱoF_ℱto,

which is the tensor form of F^𝒮_st =
F^{o}_st-F^{o}_sℱ(F^{o}_ℱℱ)^-1F^{o}_ℱt. Note
that the sub-matrix (F^{o}_ℱℱ)^-1  is
non-singular. This comes from the fact that F^{o} is an
inverse M-matrix (an inverse M-matrix is a matrix whose
inverse is an M-matrix), hence each of its principal sub-matrix is also an
inverse M-matrix. We have the following statement:

 
	In the extended network G^o, F_sto is
        non-zero if and only if t is reachable from s in the
        original network G.  Furthermore,
 if the nodes in the set ℱ fail,
 F_st𝒮 is non-zero (where 𝒮=ℱ∪{o}) if and only if t is
 still reachable from s in network G after the failures.

Using the above statement and Theorem <ref>, we can answer
(static and dynamic) reachability queries both before and after
failures in constant times (for a constant size node failure set
ℱ) by pre-computing F_::o (=F^{o})
and storing the results in a table.  The method for answering
reachability queries is summarized in Algorithm (<ref>). The function
1_{b} is an indicator function which is equal to 1 if
b=True and 0 if b=False. 









§ CONCLUSION

We revisited the fundamental matrix in Markov chain theory and extended it to the fundamental tensor which we showed that can be built much more efficiently than computing the fundamental matrices separately (O(n^3) vs. O(n^4)) for the applications that the whole tensor is required. We also showed that fundamental matrix/tensor provides a unifying framework to derive other Markov metrics and find useful relations in a coherent way. We then tackled four interesting network analysis applications in which fundamental tensor is exploited to provide effective and efficient solutions: 

1) we showed that fundamental tensor unifies various network random-walk measures, such as distance, centrality measure, and topological index, via summation along one or more dimensions of the tensor; 2) we extended the definition of articulation points to the directed networks and used the (normalized) fundamental tensor to compute all the articulation points of a network at once. We also devised a metric to measure the load balancing over nodes of a network. Through extensive experiments, we
evaluated the load balancing in several specifically-shaped networks and real-world networks; 3) we showed that (normalized) fundamental tensor can be exploited to infer the cascade and spread of a phenomena or an influence in social networks. We also derived a formulation to find the most influential nodes for maximizing
the influence spread over the network using the (normalized) fundamental tensor, and demonstrated the efficacy of our method compared to other well-known ranking methods through multiple real-world network experiments; and 4) we presented a
dynamic reachability method in the form of a pre-computed oracle which is cable of answering
to reachability queries efficiently both in the case of having failures or no failure
in a general directed network.




§ ACKNOWLEDGEMENT

The research was supported in part by  US DoD DTRA grants HDTRA1-09-1-0050
and HDTRA1-14-1-0040, and ARO MURI Award W911NF-12-1-0385. We would also like to thank our colleagues, Amir Asiaei and Arindam Banerjee, who helped us with the results reported in Section <ref>.


00





elsarticle-num 















§ APPENDIX
 
In this appendix, we provide the detailed derivations regarding the
relations between the stochastic form and matrix form of hitting time
and hitting costs, respectively.

∙  Relation between the stochastic form and matrix form of hitting time

Let t be the only absorbing node and rest of nodes belong to 𝒯, then:

    H_s^{t}   =   ∑_k=1 k∑_m∈𝒯[P^k-1_𝒯𝒯]_sm[P_𝒯𝒜]_mt=∑_k=1 k∑_m∈𝒯[P^k-1_𝒯𝒯]_sm(1-∑_j∈𝒯[P_𝒯𝒯]_mj)  
       =   ∑_k=1 k(∑_m∈𝒯[P^k-1_𝒯𝒯]_sm - ∑_j∈𝒯[P^k_𝒯𝒯]_sj) = ∑_m∈𝒯∑_k=1 k([P^k-1_𝒯𝒯]_sm - [P^k_𝒯𝒯]_sm) 
       =   ∑_m∈𝒯[P^k-1_𝒯𝒯]_sm = ∑_m F^{t}_sm,

which is the matrix form of hitting time Eq.(<ref>).


∙  Relation between the stochastic form and matrix form of hitting cost

Let 𝒵_sm be the set of all possible walks from s to m
and ζ_j be the j-th walk from this set. We use
𝒵_sm(l) to denote the subset of walks whose total length
is l, and 𝒵_sm(k,l) to specify the walks which have
total length of l and total step size of k. Recall that a walk (in
contrast to a path) can have repetitive nodes, and the length of a
walk is the sum of the edge weights  in the walk and its step size is
the number of edges. Recall that
ℙ(η_t=l|X_0=s) denotes the probability of hitting t in
total length of l when starting from s, which can be obtained from
the probability of walks: ℙ(η_t=l|X_0=s)=∑_ζ_j∈
  Z_st(l)Pr_ζ_j. Probability of walk ζ_j
denoted by Pr_ζ_j is computed by the production over
the  probabilities of passing edges:
Pr_ζ_j=p_sv_1p_v_1v_2...p_v_k-1m, where
p_vu is the edge probability from v to u. The summation over
the walk probabilities is computed using the following relation: 

    ∑_ζ_j∈ Z_sm(k)Pr_ζ_j=
     
    [P_𝒯𝒯^k]_sm   if  m∈𝒯
    
    [P_𝒯𝒯^k-1P_𝒯𝒜]_sm   if  m∈𝒜

With this introduction, the derivation of the stochastic form of
hitting cost Eq.(<ref>) can proceed as follows: 



    _s^{t}   =   ∑_l∈𝒞l∑_k=1^<∞∑_ζ_j∈𝒵_st(k,l)Pr_ζ_j
       =   ∑_l∈𝒞∑_k=1^<∞∑_ζ_j∈𝒵_st(k,l)l_ζ_jPr_ζ_j
       =   ∑_ζ_j∈𝒵_stl_ζ_jPr_ζ_j
       =   ∑_ζ_j∈𝒵_stPr_ζ_j∑_k=1^k_ζ_j w_v_k-1v_k
       =   ∑_ζ_j∈𝒵_st∑_k=1^k_ζ_j[∏_i=1^kp_v_i-1v_i.(p_v_kv_k+1w_v_kv_k+1).∏_i=k+2^k_ζ_jp_v_i-1v_i]
    
       =   ∑_e_xy∈ Ep_xyw_xy(∑_ζ_j∈𝒵_sxPr_ζ_j).(∑_ζ_i∈𝒵_ytPr_ζ_i) 
       =   ∑_e_xy∈ Ep_xyw_xy(∑_k∑_ζ_j∈𝒵_sx(k)Pr_ζ_j).(∑_k∑_ζ_i∈𝒵_yt(k)Pr_ζ_i)
    
       =   ∑_e_xy∈ Ep_xyw_xy(∑_k [P_𝒯𝒯^k]_sx).(∑_k [P_𝒯𝒯^k-1P_𝒯𝒜]_yt) 
       =   ∑_e_xy∈ Ep_xyw_xyF^{t}_sx Q^{t}_y
    
       =   ∑_e_xy∈ Ep_xyw_xyF^{t}_sx
       =   ∑_x F^{t}_sx∑_y∈𝒩_out(x) p_xyw_xy
       =   ∑_x F^{t}_sx r_x,

where l_ζ_j and k_ζ_j denote the length and step size
of a  walk ζ_j, respectively, and r_x=∑_y∈𝒩_out(x) p_xyw_xy is the average outgoing cost of
node x. In the above derivation,  Eq.(<ref>) comes from
Eq.(<ref>), and Eq.(<ref>) follows from the fact that Q^{t}_y=1 when having
t as the only absorbing node in the network and reachable from all
the other nodes.  





