Network Essence: PageRank Completion and Centrality-Conforming Markov Chains
Shang-Hua Teng







Network Essence: PageRank Completion and Centrality-Conforming Markov Chains
    Shang-Hua TengSupported in
  part by a Simons Investigator Award from the Simons Foundation
  and by NSF grant CCF-1111270.
I would like to thank my Ph.D. student 
  Alana Shine and the three anonymous referees for valuable feedback.
 Computer Science and Mathematics
  USC

    Received: December 30, 2023/ Accepted: December 30, 2023
======================================================================================================================================================================================================================================================================================




Jiří Matoušek (1963-2015) had many breakthrough contributions
 in mathematics and algorithm design.

His milestone results are not only profound  but also 
  elegant.
By going beyond the original objects — 
  such as Euclidean spaces or linear programs —
  Jirka found the essence of 
  the challenging mathematical/algorithmic problems 
  as well as beautiful solutions
  that were natural to him, but were surprising discoveries to the field.

In this short exploration article, 
  I will first share with readers my initial
  encounter with Jirka and discuss one of
  his fundamental geometric results from the early 1990s.
In the age of social and information networks, 
  I will then turn the discussion from 
  geometric structures to network structures,
  attempting to take a humble step towards the holy grail of network science,
  that is to understand the network essence 
  that underlies the observed sparse-and-multifaceted network data.
I will discuss a simple result which summarizes some basic 
   algebraic properties of personalized PageRank matrices.
Unlike the traditional transitive closure of binary relations, 
  the personalized PageRank matrices take “accumulated Markovian closure” 
  of network data. 
Some of these algebraic properties are known in various contexts.
But I hope featuring them together in a broader context
   will help to illustrate
  the desirable properties of this Markovian completion of networks,
  and motivate systematic developments of a network theory
  for understanding vast and ubiquitous multifaceted network data.










§ GEOMETRIC ESSENCE: TO THE MEMORY OF JIŘÍ MATOUŠEK


Like many in theoretical computer science and discrete mathematics,
  my own research has benefited from Jirka's deep insights, 
  especially into computational geometry <cit.>
  and linear programming <cit.>.
In fact, our paths accidentally crossed 
  in the final year of my Ph.D. program.
As a part of my 1991 CMU thesis <cit.>, 
I obtained a result on the deterministic computation of 
  a geometric concept, called centerpoints, which led me to
  learn about one of Jirka's groundbreaking results during
  this time.




 §.§ Centerpoints



The median is a widely-used concept for analyzing one-dimensional data,
  due to its statistical robustness
  and its natural algorithmic applications to divide-and-conquer.
In general, suppose P = {p_1,...,p_n} is a set of n real numbers.
For δ∈ (0,1/2], we call c∈ 
  a δ-median of P
  if max(|{i : p_i< c}|,|{j : p_j> c}|)≤ (1-δ) n.
A 1/2-median of P is known simply as a median.
Centerpoints are high-dimensional generalization of medians:


Suppose P = {_1,…,_n} is a point set 
  in d. 
For δ∈ (0,1/2], a point ∈d
  is a δ-centerpoint of P if 
  for all unit vectors ∈d,
the projection ^T is a δ-median
 of the projections, ^T· P = {^T_1,…,^T_n}.


Geometrically, every hyperplane  in d divides 
 the space into two open halfspaces,
 ^+ and ^-. 
Let the splitting ratio of  over P,
denoted by δ_(P), be:

    δ_(P) := max(|^+∩ P|,|^-∩ P|)/|P|

Definition <ref>
  can be restated as:
  ∈^d is a δ-centerpoint of P
  if the splitting ratio of every hyperplane  passing through  
  is at most (1-δ).
Centerpoints are fundamental to geometric divide-and-conquer 
   <cit.>.
They are also strongly connected  to the concept of regression 
  depth introduced by Rousseeuw and 
  Hubert in robust statistics  <cit.>.

We all know that every set of real numbers has a median.
Likewise — and remarkably —
  every point set in d-dimensional Euclidean space
  has a 1/d+1-centerpoint
 <cit.>.
This mathematical result can be established by 
  Helly's  classical theorem from convex 
  geometry.[Helly's Theorem states: 
  Suppose  is a family of at least d+1 convex sets
  in ^d, and  is finite or each member  
  of  is compact.  
Then, if each d+1 members of  
  have a common point, there must be a point
  common to all members of .]
Algorithmically,
  Vapnik-Chervonenkis' celebrated sampling theorem <cit.> (more below)
  implies an efficient randomized algorithm  — at least in theory — 
  for computing a (1/d+1-ϵ)-centerpoint.
This “simple” algorithm first takes a “small”random sample, and then
  obtains its 1/d+1-centerpoint via linear programming.
The complexity of this LP-based sampling algorithm is:

    2^O(d)( d/ϵ^2·logd/ϵ)^d.




 §.§ Derandomization


For my thesis,  I needed to compute centerpoints 
  in order to construct geometric separators <cit.>
  for supporting finite-element simulation and
   parallel scientific computing <cit.>.
Because linear programming was too slow, I needed 
  a practical centerpoint algorithm to run large-scale 
  experiments <cit.>.
Because I was a theory student, I was also aiming
   for a theoretical algorithm to enrich my thesis.
For the latter, I focused on derandomization, which was then
  an active research area in theoretical computer science.
For centerpoint approximation without linear programming, 
  my advisor Gary Miller and I quickly obtained a simple 
  and practical algorithm[The construction started 
  as a heuristics, but it took a few more 
  brilliant collaborators  and years (after my graduation) to rigorously 
  analyzing its performance <cit.>.] 
  based on Radon's classical theorem[Radon's Theorem states: Every point set Q⊂^d with |Q| ≥ d + 2 can be 
 partitioned into two subsets  (Q_1,Q_2) such that 
 the convex hulls of Q_1 and Q_2 have a common point.
]
  <cit.>.
But for derandomization, it took me more than a year to finally design 
  a deterministic linear-time algorithm 
  for computing (1/d+1-ϵ)-centerpoints 
  in any fixed dimensions.
It happened in the Spring of 1991, my last semester at CMU.
Gary then invited me to accompany him 
  for a month-long visit, starting at the spring break of 1991,
  at the International Computer Science Institute (ICSI),
  located near the U.C. Berkeley campus.
During the  California visit, 
I ran into Leo Guibas, 
  one of the pioneers of computational geometry.

After I told Leo about my progress on  Radon-Tverberg 
  decomposition <cit.> and centerpoint computation,
  he mentioned to me a paper by Jirka <cit.>,
  which was just accepted to the
  ACM Symposium on Theory of Computing (STOC 1991) 
  —  before my solution  —  that beautifully solved the 
  sampling problem for a broad class of
  computational geometry and statistical learning problems.

Jirka's result — see Theorem <ref> below — 
  includes the approximation of centerpoints as a simple special case.
Although our approaches had some ideas in common, 
  I instantly knew that this mathematician —
  who I later learned was just a year older than me —
  was masterful and brilliant. 
I shortened that section of my thesis
 by referring readers to Jirka's paper <cit.>,
 
  and only included the scheme I had
  that was in common with his bigger result.








 §.§ Matoušek's Theorem: The Essence of Dimensionality

Mathematically, a range space Σ is a pair ( X ,  ), 
  where X is a finite or infinite set,
  and  is a finite or infinite family of subsets of X. 
Each H∈ can be viewed as a classifier of X, with elements
  in X ∩ H as its positive instances.
For example, d and its halfspaces form a range space,
  so do d and its L_p-balls, for any p> 0, 
  as well as V and the set of all cliques in a graph G = (V,E).
Range spaces greatly extend the concept of linear separators.

An important technique in statistical machine learning and computational geometry
  is sampling.
For range spaces, we can measure the quality of a sample as the following:

Let Σ = (X,) be an n-point range space.
A subset S ⊆ X is an ϵ-sample 
  or ϵ-approximation for Σ if for all H∈: 

    | |H∩ S|/|S| - |H∩ X|/|X|| ≤ϵ



For each S ⊆ X, the set of distinct classifiers
   that  can define is (S) = {H∩ S: H∈}.
For any m≤ |X|, let the shatter function for Σ be:

    π_(m) = sup_S⊆ X, |S| = m|(S)|




Let Σ = (X, )
   be an n-point range space 
    with the shatter function satisfying 
π_(m) = O(m^d) (d≥ 1 a constant). 
Having a subspace oracle for Σ, and given a parameter r, we can 
  deterministically compute a (1/r)-approximation of size
  O(dr^2log r) for Σ, in time O(n(r^2log r)^d).


Matoušek's sampling theorem goes beyond traditional geometry 
  and completely derandomizes the theory of Vapnik-Chervonenkis <cit.>.

 
There exists a constant c such that 
  for any finite range space Σ =(X,) 
  and ϵ, δ∈(0,1), if S is a set of 
c·d/ϵ^2(logd/ϵδ))
 uniform and independent samples
 from X, where d = (Σ), then:

≥ 1 -δ



Matoušek's deterministic algorithm
  can be applied to geometric classifiers 
  as well as any classifier — known as a
 concept space — 
  that arises in statistical learning theory <cit.>.
The concept of range space has also provided a powerful tool for 
  capturing geometric structures, and played a profound role — both in theory
  and in practice — for data clustering <cit.> and
 geometric approximation <cit.>.
The beauty of 
  Vapnik-Chervonenkis' theory and Matoušek's sampling theorem
  lies in the essence of dimensionality,
  which is generalized from geometric spaces to abstract range spaces.
In Euclidean geometry, the dimensionality comes naturally
  to many of us.
For abstract range spaces, the growth of the shatter functions
  is more intrinsic!





If π_(m) = 2^m, then there exists a set S⊆ X
  of m elements that is shattered, i.e., 
  for any subset T of S ⊆ X, there exists
  H∈ such that T = H ∩ S.
In other words, we can use  to build classifiers for
   all subsets of S.
There is a beautiful dichotomy of polynomial and exponential
  complexity within the concept of shattering:


  * either X has a subset S ⊆ X of size m that can be shattered
  by ,

  * or for any U ⊆ X, |U| ≥ m, 
  |{H∩ U: H∈}| is polynomial in |U|.

The latter case implies that  can only be used to build
 a polynomial number of classifiers for U.
The celebrated VC-dimension of range space Σ = (X,),
denoted by 
(Σ), is defined as: 

    (Σ) := {m:  π_(m) = 2^m}.

This polynomial-exponential dichotomy is 
  established by the following
  Sauer's lemma.[This lemma is also
known as Perles-Sauer-Shelah's lemma.]


For any range space  Σ = (X,) and ∀ m> (Σ), 
π_(m) ≤∑_k=0^(Σ)m  k.


Sauer's lemma extends the following well-known fact
  of Euclidean geometry:
   any set of   m hyperplanes in d divides the space into 
  at most O(m^d) convex cells.
By the point-hyperplane duality, any set of m points can be divided
  into at O(m^d) subsets by halfspaces.

Although  my construction of ϵ-samples in d 
  was good enough for designing linear-time 
  centerpoint approximation algorithm in fixed dimensions,
  it did not immediately generalize to arbitrary range spaces, 
   because it was tailored to the
   geometric properties of Euclidean spaces.

By addressing abstract range spaces, 
  Jirka resolved the intrinsic algorithmic problem at the heart 
  of  Vapnik-Chervonenkis' sampling theory.
Like Theorem <ref>,
  many of Jirka's other landmark and breakthrough
  results are elegant, insightful, and fundamental.
By going beyond the original objects
  — such as Euclidean spaces or  linear programs <cit.> —
  Jirka usually went directly to the essence of 
  the challenging problems to come up with beautiful solutions
  that were natural to him but remarkable 
  to the field.






§ BACKGROUNDS: UNDERSTANDING MULTIFACETED NETWORK DATA


To analyze the structures of social and information networks
  in the age of Big Data, we need to overcome
  various conceptual and algorithmic challenges both in understanding
  network data and in formulating solution concepts.
For both, we need to capture the network essence.



 §.§ The Graph Model  — A Basic Network Facet


At the most basic level, 
  a network can be modeled as a graph G = (V,E),
  which characterizes the structure of the network
  in terms of:


  * nodes: for example, Webpages, Internet routers,
  scholarly articles, people,  random variables, or counties

  * edges: for example, links, connections, citations, friends, conditional dependencies,  or voting similarities

In general, nodes in many real-world networks may not be 
  “homogeneous” <cit.>, 
  as they may have some additional features, specifying 
  the types or states of the node elements.
Similarly, edges may have additional features, specifying
  the levels and/or types of 
  pairwise interactions, associations, or affinities.

Networks with  “homogeneous” types of nodes and edges are closest to
  the combinatorial structures studied under traditional graph theory, which 
  considers both weighted or unweighted graphs.
Three basic classes of weighted graphs 
  often appear in applications.  
The first class consists of distance networks,
  where each edge e∈ E is assigned a number l_e≥ 0,
  representing the length of edge e.
The second class consists of affinity networks,
  where each edge (u,v) ∈ E is assigned a  weight w_u,v≥ 0,
  specifying u's affinity weight towards v.
The third class consists of probabilistic networks,
  where each (directed) edge (u,v) ∈ E is assigned a probability 
  p_u,v≥ 0, modeling how a random process  connects u to v.
It is usually more natural to view
    maps or the Internet  as distance networks,
    social networks as affinity networks, and 
    Markov processes as  probabilistic networks.
Depending on applications, a graph may be directed or undirected.
Examples of directed networks include:
 the Web, Twitter, the citation graphs of scholarly publications, 
  and Markov processes.
Meanwhile, Facebook “friends” or collaboration networks 
  are examples of undirected graphs.

In this article, we will first focus on affinity networks.
An affinity network with n nodes can be mathematically represented
   as a weighted graph  G = (V,E,).
Unless otherwise stated, we assume 
  V = [n] and  is an n× n non-negative matrix (for example from 
[0,1]^n× n).
We will follow the convention that for i≠ j, w_i,j = 0,
  if and only  if, (i,j)∉E.
If  is a symmetric matrix, then we say G  is undirected.
If w_i,j∈{0,1}, ∀ i,j∈ V,  
  then we say G is unweighted. 

Although they do not always fit, 
  three popular data models for defining pairwise affinity weights 
  are the metric model, feature model, and statistical model.
The first assumes that an underlying metric space,
  = (V,),
   impacts the interactions among nodes in a network.
The affinities  between nodes may 
   then be determined by their distances from
  the underlying metric space:
The closer two elements are, the higher their affinity
  becomes, and the more interactions they have.  
A standard way to define affinity  weights for  u≠ v is: 
w_u,v = (u,v)^-α,
  for some α > 0.
The second assumes   that there exists an underlying “feature” space,
  = (V, ),
  that impacts the interactions among nodes in a network.
This is a widely-used alternative data model for information networks.
In a d-dimensional feature space,  is an n× d matrix, where
  f_u,i∈+∪{0} denotes u's quality score 
   with respect the i^th feature.  
Let _u denote the u^th row of , i.e., 
  the feature vector of node u.
The affinity weights  w_u,v between two nodes u and v may 
  then be determined by the correlation between
  their features:
w_u,v∼(_u^T·_v) = ∑_i=1^d f_u,i· f_v,i.
The third assumes that there exists an underlying 
  statistical space (such as a stochastic block model, Markov process, or (Gaussian) random field)
  that impacts the pairwise interactions.
The higher the dependency between two elements is, the higher their 
 strength of tie is.

If one thinks that the meaning of weighted networks is complex, the 
  real-world network data is far more complex and diverse.
We will have more discussions in Section <ref> and
 Section <ref>.




 §.§ Sparsity and Underlying Models
 

A basic challenge in network analysis is that
  real network data that we observe is only a reflection of
  underlying network models.
Thus, like machine learning tasks which have to work 
  with samples from an unknown underlying distribution,
  network analysis tasks typically work 
  with observed network data, 
  which is usually different from the underlying network model.
As argued in 
  <cit.>, 
  a real-world  social and information network may be viewed as an
   observed network, induced by a “complete-information”  underlying 
   preference/affinity/statistical/geometric/feature/economical model.
However, these observed 
   networks are typically sparse with many missing links.


For studying network phenomena, it is crucial to mathematically
   understand underlying network models, while 
  algorithmically work efficiently with sparse observed data. 
Thus, developing systematic approaches to uncover or 
  capture the 
  underlying network model — or the network essence — is 
  a central and challenging mathematical task  in network analysis.


Implicitly or explicitly, underlying network models are the ultimate
  guide for understanding network phenomena, and
  for inferring missing network data, and distinguishing missing links
  from absent links.
To study basic network concepts, we also need to simultaneously
  understand the observed and underlying networks.
Some network concepts, such as centrality, capture 
 various aspects of “dimension reduction” of network data.
Others characterizations, 
  such as  clusterability  and community classification,
  are more naturally expressed in 
  a space with  dimension higher than that of the observed networks. 

Schematically, centrality assigns a numerical score or ranking
  to each node, which measures the importance
  or significance of each node in a network 
  <cit.>.
Mathematically, a numerical centrality measure is a mapping from
  a network G=(V,E,) to a |V|-dimensional real vector:

    [ _(v) ]_v∈ V∈^|V|


For example, a widely used centrality measure is the 
  PageRank centrality.
Suppose G = (V,E,) is a weighted directed graph.
The PageRank centrality uses an
   additional parameter α∈ (0,1) —
   known as the restart constant —
   to define a finite Markov process whose transition rule
  — for any node v∈ V — is the following:


  * with probability α, restart at a random node in V, and

  * with probability (1-α),
   move to a neighbor of v,  chosen randomly with probability
   proportional to edge weights out of v.

Then, the  PageRank centrality (with restart constant α)
  of any v∈ V  is proportional to
 v's stationary probability in this Markov chain.

In contrast, clusterability
  assigns a numerical score or ranking to each subset of nodes,
  which measures the coherence
  of each group in a network <cit.>.
Mathematically, a numerical clusterability measure
 is a mapping from a network G = (V,E,)
 to a 2^|V|-dimensional real vector:

    [ _(S) ]_S⊆ V∈ [0,1]^2^|V|

An example of clusterability measure is
  conductance 
  <cit.>.[The conductance of 
  a group S⊂ V is the ratio of its external connection to its
  total connection in G.]
Similarly, a community-characterization rule <cit.> 
 is a mapping from a network G = (V,E,)
 to a 2^|V|-dimensional Boolean vector:

    [ _(S) ]_S⊆ V∈{0,1}^2^|V|

indicating whether or not each group S⊆ V is a community
  in G.
Clusterability and community-identification rules
  have much higher dimensionality than centrality.
To a certain degree, they can be viewed as a 
  “complete-information” model of the observed network.
Thus again:

Explicitly or implicitly,
  the formulations of these network 
  concepts are  mathematical processes
  of uncovering or capturing underlying network models.







 §.§ Multifaceted Network Data: Beyond Graph-Based Network Models




Another basic challenge in network analysis
  is that 
  
  real-world network  data is 
  much richer than the graph-theoretical representations.
For example, social networks are more than weighted graphs. 
Likewise, the Web and Twitter are not just  directed graphs.  
In general, network interactions and phenomena 
  — such as social influence <cit.> or electoral behavior
 <cit.>, —    are more complex than 
  what can be captured by nodes and edges.
The network interactions are often the result of the interplay between 
  dynamic mathematical processes and static underlying graph structures 
  <cit.>.




  §.§.§ Diverse Network Models


The richness of network data and diversity of network concepts
  encourage us to consider network 
  models beyond graphs <cit.>.
For example, 
  each clusterability measure
  [_(S)]_S⊆ V of a weighted graph 
  G=(V,E,) explicitly 
  defines a complete-information, weighted hyper-network:


A weighted hypergraph over V  is given by H = (V,E,τ)
  where E⊆ 2^V is a set of hyper-edges and 
  τ: E → is a function 
  that assigns weights to hyper-edges.
H is a complete-information cooperative networks if
  E= 2^V.


We refer to weighted hypergraphs as cooperative networks 
  because they are the central subjects 
  in classical cooperative game theory, but under
   a different name <cit.>.
An n-person cooperative game over V = [n]
  is specified by a characteristic function
  τ: 2^V →,
  where for any coalition S⊆ V,
  τ(S) denotes the cooperative utility  of  S.

Cooperative networks are generalization of undirected weighted graphs.
One can also generalize directed networks,
  which specify directed node-node interactions.
The first one below explicitly captures
  node-group interactions,
  while the second one captures group-group interactions.


An incentive network over V is a pair U = (V,u).
For each s ∈ V, 
  u_s: 2^V∖{s}→ 
  specifies s's incentive utility
  over subsets of V∖{s}.
In other words, there are |S| utility values, 
  {u_s(S ∖{s}}_s∈ S,
  associated with each group S⊆ V in
  the incentive network. 
For each s∈ S, the value
   of its interaction with the rest of the group
  S ∖{s} is explicitly 
  defined as u_s(S ∖{s}).



A powerset network over V is a weighted directed
  network on the powersets of V.
In other words, a powerset network P = (V,θ)
 is specified by a function
  θ: 2^V× 2^V →.


For example — as pointed in <cit.> —
  a social-influence instance fundamentally defines
  a powerset network.
Recall that a social-influence instance 
   is specified by a directed graph G=(V,E) 
   and an influence model 
  <cit.>, where
G defines the graph structure of the social network
  and  defines a stochastic process that characterizes
  how nodes in each seed set S⊆ V  
  collectively influence  
  other nodes using the edge structures of G <cit.>.
A popular influence model is 
  independent cascade (IC)[
In the classical IC model, each directed edge (u,v) ∈ E
  has an influence probability p_u,v∈ [0,1].
The probability profile defines a discrete-time influence process
  when  given a seed set S:
At time 0,  nodes in S are activated  while other nodes are inactive.
At time t ≥ 1,
   for any node u activated at time t-1, it has one
   chance to activate each of its inactive out-neighbor
   v with an independent probability of p_u,v.
When there is no more activation,
  this stochastic process ends with a random set 
  of nodes activated during the process.
] <cit.>.


Mathematically, the influence process  and the network structure G
  together define a probability distribution 
  P_G,: 2^V× 2^V→ [0,1]:

For each T ∈ 2^V, 
 P_G,[S,T] 
 specifies the probability that T is the final activated set 
  when S cascades its influence through the network G.
Thus, P_=(V,P_G,) defines a natural powerset network,
  which can be viewed as the underlying network
  induced by the interplay between the static network structure G and dynamic influence process .

An important quality measure of S in this process is S's  
  influence spread  <cit.>.
It can be defined from the powerset model P_=(V,P_G,) 
  as following:

    σ_G,(S) = ∑_T⊆ V |T|·P_G,[S,T].

Thus, (V,σ_G,) also defines a natural 
  cooperative network <cit.>.

In many applications and studies, ordinal network models
   rather than cardinal network models
  are used to capture the preferences among nodes.
Two classical applications of preference frameworks
  are voting 
   <cit.> and stable marriage/coalition formation
  <cit.>.
A 
  modern use of preference models is
  the Border Gateway  Protocol (BGP) 
  for network routing 
  between autonomous  Internet systems  <cit.>.

In a recent axiomatic study of community identification in social networks, 
  Borgs et al. <cit.>
  considered the following abstract social/information
   network framework. 
Below, for a non-empty finite set V, let 
  denote the set of all linear orders on V.



A preference network over V is a pair A = (V,Π), where


 Π ={π_u}_u∈ V∈^|V| 
 is a preference profile in which π_u 
 specifies  u's individual preference.





  §.§.§ Understanding Network Facets and Network Concepts


Each network model enables us to focus on 
   different facets of network data.
For example, 
  the powerset model offers the most natural framework for capturing
  the underlying interplay between influence processes 
  and network structures.
The cooperative model matches the explicit representation 
  of clusterability, group utilities, and influence spreads.
While traditional graph-based network data often consists solely of 
  pairwise interactions, affinities, or associations,  
  a community is formed by a group of individuals.







Thus, the basic question for community identification is to understand
  “how do individual preferences (affinities/associations) 
  result in group preferences or community coherence?” <cit.>
The preference model highlights
  the fundamental aspect of community characterization.
The preference model is also natural for addressing the
  question of summarizing individual preferences 
  into one collective preference, which is 
  fundamental in the formulation of network centrality <cit.>.
Thus, studying network models beyond graphs 
   helps to broaden our understanding of social/information networks.

Several these network models, as defined above, are
  highly theoretical models.
Their complete-information profiles have exponential dimensionality
  in |V|.
To use them as underlying models in network analysis,
  succinct representations should be constructed to efficiently
  capture observed network data.
For example, both the conductance clusterability measure
  and the social-influence powerset network are succinctly defined.
Characterizing network concepts in these models and 
  effectively applying them 
  to understanding real network data
  are promising and fundamentally challenging 
  research directions in network science.











§ PAGERANK COMPLETION
  


Network analysis is a task to capture the essence of the observed networks.
For example, graph embedding <cit.> 
  can be viewed as a process to 
  identify the geometric essence of networks.
Similarly, network completion 
  <cit.>,   
  graphon estimation 
  <cit.>, and
  community recovering in hidden stochastic block models <cit.>
  can be viewed as processes to distill the statistical essence
  of networks.
All these approaches build constructive maps
  from observed sparse
  graphs to underlying complete-information models.
In this section, we study the following basic question:


Given an observed sparse affinity network G= (V,E,), 
 can we construct a complete-information affinity network 
  that is consistent with G?



This question is simpler than but relevant to matrix and network completion 
  <cit.>,
  which aims to infer the missing data from sparse, observed network data.
Like matrix/network completion,
  this problem is mathematically an inverse problem.

Conceptually, we need to formulate the meaning of 
“a complete-information affinity network consistent with G.”

Our study is also partially motivated by the following question asked in
<cit.>, aiming to deriving personalized 
  ranking information from graph-based network data:

Given a sparse affinity network G= (V,E,), 
 how should we construct a complete-information preference model 
 that best captures the underlying individual preferences
 from network data given by  G?








We will prove 
  the following basic structural result[See Theorem <ref> for the 
  precise statement.]:
Every connected, undirected, weighted graph  G= (V,E,)
 has an undirected and weighted
   graph = (V,,), such that:


  * Complete Information: 
    forms  a complete graph with |V| self-loops.

  * Degree and Stationary Preserving:  
 ·1 = ·1. Thus, 
  the random-walk Markov chains on G and on  
  have the same stationary distribution.

  * PageRank Conforming: 
The transition matrix _ of the random-walk 
  Markov chain on   is conformal to the PageRank of G,
  that is, _^T·1 is proportional to the 
  PageRank centrality  of G

  * Spectral Approximation: 
  G and  are spectrally similar.
 


In the last condition, the similarity between G and  
  is measured by the following 
  notion of spectral similarity 
  <cit.>:

Suppose G = (V,E,) and = (V,,) 
  are two weighted undirected graphs  over the same set V of n nodes.
Let  _ = _ - and 
  _ = _- 
  be  the Laplacian matrices, respectively, of these two 
  graphs.
Then, for σ≥ 1, we say 
   G and  are σ-spectrally similar
  if:

    ∀∈n,   1/σ·^T_≤^T_≤σ·^T_


Many graph-theoretical measures, such as flows, cuts, 
  conductances, effective resistances, 
  are approximately preserved 
  by spectral similarity <cit.>.
We refer to = (V,,) 
  as the PageRank essence or PageRank completion 
  of G = (V,E,).



 §.§ The Personalized PageRank Matrix


= (V,,) stated above is derived from 
  a well-known structure in network analysis, the personalized 
  PageRank matrix  of a network <cit.>.



  §.§.§ Personalized PageRanks


Generalizing the Markov process of PageRank, 
  Haveliwala <cit.> introduced 
   personalized PageRanks.
Suppose G = (V,E,) is a weighted directed graph 
  and α > 0 is a restart parameter.
For any distribution ß over V,
 consider the following Markov process,
   whose transition rule —  for  any v∈ V — is the following:


  * with probability α, restart at a random node in V
  according to distribution ß, and

  * with probability (1-α),
   move to a neighbor  of v, 
   chosen randomly with probability
   proportional to edge weights out of v.

Then, the PageRank with respect to the
   starting vector ß, 
  denoted by _ß,
  is the stationary  distribution of this Markov chain.

Let d^out_u = ∑_v∈ V w_u,v

    denotes the out-degree

  of u∈ V in G.

Then,  _ß is the solution to the following equation:

    _ß = α·ß + (1-α)
      ·^T·(_^out)^-1·_ß

where  _^out =  diag([d_1^out,...,d_n^out]) is
  the diagonal matrix of
  out degrees.
Let 1_u denote the n-dimensional  vector
  whose u^th location is 1 and all other entries in 
  1_u are zeros.
Haveliwala <cit.> referred to _u := _1_u 
  as the personalized PageRank of u∈ V in G.
Personalized PageRank is asymmetric, and hence to emphasize this fact,
 we express _u as:

    _u = (u1, ⋯, un)^T.

Then {_u}_u∈ V — the personalized PageRank profile —
   defines  the following  matrix:

The personalized PageRank matrix of an
   n-node weighted graph  G = (V,E, ) and restart constant α > 0 is:

    _,α = 
    [_1,...,_n]^T
    =
    [
    [ 11  ⋯ 1n;  ⋮  ⋯  ⋮; n1  ⋯ nn;    ]]



In this article, we normalize the PageRank centrality so that
  the sum of the centrality values over all nodes is equal to n.
Let 1 denote  the n-dimensional vector of all 1s.
Then, the PageRank centrality of G is the solution to the
  following Markov random-walk
   equation <cit.>:

    ,α = α·1 + (1-α)
      ·^T(_^out)^-1,α


Because 1 = ∑_u 1_u, we have: 

For any G = (V,E,) and α > 0:

    ,α = ∑_u∈ V_u = 
      _,α^T ·1



Because Markov processes preserve 
   the probability mass of the starting vector, we also have:


For any G = (V,E,) and α > 0, _,α 
 is non-negative and:

    _,α·1 = 1



In summary, the PageRank matrix _,α
  is a special matrix  associated with network G — its row sum is the
  vector of all 1s and its column sum is the PageRank  centrality of G.



 §.§ PageRank Completion of Symmetric Networks


PageRank centrality and personalized PageRank matrix 
  apply to both directed and undirected weighted graphs.
Both Proposition <ref> and Proposition <ref>
  also hold generally.
In this subsection, we will focus mainly on undirected weighted networks.

In such a case, let _ be the diagonal matrix associated
  with weighted degrees _ = ·1 and
  let _ = _^-1 be 
  the standard random-walk transition matrix  on G.

To state the theorem below, let's first review a basic concept
  of Markov chain.
Recall that a Markov chain over V is defined by
  an n× n transition matrix  satisfying 
  the stochastic condition:  is non-negative and
·1 = 1.
A probability vector  is the stationary distribution of
  this Markov process if:

    ^T =

It is well known that 
  every irreducible and ergodic Markov chain has a stationary distribution.
Markov chain  is detailed-balanced  if:

    [u] [u,v] = [v] [v,u],   ∀ u,v∈ V


We will now prove the following structural result:

For any weighted directed graph G = (V,E,)  and restart constant α > 0:


  A:
_,α and (_^out)^-1·
  have the same eigenvectors. 
  Thus, both Markov chains have the same stationary distribution.

  B: _,α is detailed-balanced
  if and only if  is symmetric. 

Furthermore, when  is symmetric, let 
  _α= (V,_α,_α) be the
  affinity network such that:

    _α = _·_,α     ={(u,v): _α[u,v] > 0}

Then, _α satisfies the following conditions:


  * Symmetry Preserving: 
  ^T =, i.e., _α is an undirected affinity network.

  * Complete Information: If G is connected, then
  _α is a 
  complete graph with |V| self-loops.

  * Degree and Stationary Preserving:  
·1 = ·1. Thus, _ = _
  and the random-walk Markov chains _ and _ 
   have the same stationary distribution.

  * Markovian and PageRank Conforming: 

    _·1 = 1
        _^T·1 = ,α


  * Simultaneously Diagonalizable:
For any symmetric ,
  recall  _ = _- denotes the Laplacian matrix associated
  with .
Let _ = 
_^-1/2__^1/2  = 
   - _^-1/2_^-1/2
be the normalized Laplacian matrix associated with .
Then,  _ and _ are simultaneously diagonalizable.

  * Spectral Densification and Approximation: 
For all ∈n:

    α·_≤^T (1/1-α·_)≤1/α_
    α·_≤^T (1/1-α·_) ≤1/α_

In other words,
  G and 1/1-α·_α are 
  1/α-spectrally similar.



Remarks
We rescale _ and _
  by 1/1-α because _α has self-loops of 
  magnitude α_. 
In other words,
 _α only uses (1-α) fraction of its 
 weighted degrees for connecting different nodes in V.


Let n = |V|.
For any initial distribution ß over V, we 
  can explicitly express _ß as:

    _ß = α∑_k=0^∞ (1-α)^k 
    ·(^T·(_^out)^-1)^k ·ß


Consequently: we can express _,α as:
 
    _,α
     = α∑_k=0^∞ (1-α)^k 
    ·((_^out)^-1·)^k

Note that α∑_k=0^∞ (1-α)^k  = 1.
Thus, _,α is 
  a convex combination of (multi-step) random-walk 
  matrices defined by (_^out)^-1·.
Statement A 
  follows directly from the fact that 
  ((_^out)^-1·)^k 
  is a stochastic matrix for any integer  k≥ 0.

The following fact is well known <cit.>:

Suppose  is a Markov chain with stationary distribution .
Let Π be the diagonal matrix defined by .
Then, ^TΠ is symmetric if and only if
  the Markov process defined by  is  detailed balanced.



We now assume = ^T.
Then,  Eqn. (<ref>) becomes:
 
    _,α
     = α∑_k=0^∞ (1-α)^k 
    ·(_^-1·)^k

The stationary distribution of _^-1 — and 
 hence of _,α — 
  is proportional to = ·1.
_,α is detailed balanced because 
  =  _·_,α is a symmetric matrix.
Because ((_^out)^-1·)^k (for all positive integers) have
  a common stationary distribution, _,α is not detailed balanced when 
   is not symmetric.
It is also well known — by Eqn. (<ref>) — that
 for all u,v∈ V, 
  _,α[u,v] is equal to the probability that a run 
  of random walk starting at u passes by v immediately 
  before it restarts.
Thus, when G is connected, 
  _,α[u,v]>  0 for all u,v∈ V.
Thus, (_α) = n^2, and 
  _α, the nonzero pattern of  _α, is a 
  complete graph with |V| self-loops.
We have now established Condition B and Conditions 1 - 4.

We now prove Conditions 5 and 6.[Thanks to Dehua Cheng 
 of USC for assisting this proof.]
Recall that when = ^T, 
  we can express the personalized PageRank matrix as:
 
    _,α   = α∑_k=0^∞ (1-α)^k 
    ·(_^-1·)^k.


Thus: 

    _α   =  _·_,α
      =  (α∑_k=0^∞ (1-α)^k ·_·(_^-1)^k).

We compare the Laplacian matrices associated with  and :

    _    =    _ -  = _^1/2( - _^-1/2_^-1/2)_^1/2
     = _^1/2__^1/2.
    _    =    _ -  
     =  _^1/2__^1/2

where 

    _ =  - α∑_k=0^∞ (1-α)^k · 
    (_^-1/2_^-1/2)^k.

Let λ_1 ≥λ_2≥ ... ≥λ_n be the n eigenvalues
  of _^-1/2_^-1/2.
Let _1, ..., _n  
  denote the unit-length eigenvectors of _^-1/2_^-1/2 
  associated with 
  eigenvalues λ_1, ⋯, λ_n, respectively.
We have |λ_i|≤ 1.
Let Λ be the diagonal matrix associated with (λ_1,...,λ_n) and U = [_1,...,_n].
By the spectral theorem — i.e., the eigenvalue decomposition for symmetric matrices —
  we have:

    ^T_^-1/2_^-1/2    =    Λ
    ^T  =  ^T     =

Therefore:

    _    =    _^1/2^T
      ( - _^-1/2_^-1/2)^T_^1/2
        =    _^1/2( - ^T_^-1/2_^-1/2)^T_^1/2
        =   _^1/2( - Λ)^T_^1/2.

Similarly:

    __α    =    _ - _α 
    = _^1/2__^1/2
        =    _^1/2(
     - α∑_k=0^∞ (1-α)^k · 
     (_^-1/2_^-1/2)^k)
    _^1/2
        =    _^1/2(
     - α∑_k=0^∞ (1-α)^k ·^T (_^-1/2_^-1/2)^k)
    ^T_^1/2
        =    _^1/2(
     - α∑_k=0^∞ (1-α)^k ·Λ^k
    )
    ^T_^1/2
        =    _^1/2(
     - α/ - (1-α)Λ)
    ^T_^1/2.

The derivation above has proved  Condition (5).
To prove Condition (6), consider an arbitrary
  ∈n∖{0}.
With = ^T_^1/2, we have:

    ^T1/1-α_/^T_    =    1/1-α·^T_^1/2( - α/ - (1-α)Λ)
     ^T_^1/2/^T_^1/2( - Λ)^T_^1/2
    
        =    1/1-α·^T
    ( - α/ - (1-α)Λ)
    /^T( - Λ)

This ratio is in the interval of:

    [inf_λ: |λ|≤ 11/1-(1-α)λ,
    sup_λ: |λ|≤ 11/1-(1-α)λ]
    = [1/2-α,1/α].





 §.§ PageRank Completion, Community Identification, and Clustering


PageRank completion has an immediate application to 
  the community-identification approaches developed in <cit.>.
This family of methods first constructs a preference network from
  an input weighted graph G = (V,E,).
It then applies various social-choice aggregation functions 
  <cit.> to define
  network communities <cit.>.
In fact, Balcan et al <cit.> show that 
 the PageRank completion of G  provides a wonderful scheme
  (see also  in Definition <ref>)
  for constructing preference networks from affinity networks.

In addition to its classical connection with PageRank centrality, 
  PageRank completion also has 
  a direct connection with network clustering.
To illustrate this connection, let's recall a well-known  approach in spectral graph theory for clustering
<cit.>:



Both in theory and in practice, 
  the most popular vectors used in Sweep are:


  * Fiedler vector: the eigenvector associated with the
  second smallest eigenvalue of the Laplacian matrix _ <cit.>.

  * Cheeger vector: _^-1/2v_2, where v_2 is the eigenvector associated with the
  second smallest eigenvalue of the normalized Laplacian matrix _ 
  <cit.>.


The sweep-based clustering method and Fiedler/Cheeger vectors
  are the main subject of following
   beautiful theorem <cit.> in spectral graph theory:



For any symmetric weighted graph G = (V,E,),  
  let λ_2 be the second smallest eigenvalue of
 the normalized Laplacian matrix _ of G.

Let v_2 be the eigenvector associated with λ_2
   and S =  Sweep(G, _^-1/2_2).
Then: 

    λ_2/2≤_(S) ≤√(2λ_2)








By Theorem <ref>, 
 the normalized Laplacian matrices of G and its PageRank completion
  are simultaneously diagonalizable.
Thus, we can also use the eigenvector of the PageRank completion of G
  to identify a cluster of G whose conductance is guaranteed by the 
  Cheeger's inequality.


                                                      
Then, how is the PageRank completion necessarily a better representation
  of the information contained in the original network?        

For example, with respect to network clustering, what desirable properties
  does the PageRank completion have that the original graph doesn't?



While we are still looking for a comprehensive answer to these questions,
  we will now use the elegant result of 
  Andersen, Chung, and Lang <cit.>
  to illustrate that the PageRank completion indeed contains more direct
  information about network clustering than the original data .
Andersen et al proved that if one applies sweep 
to vectors {^-1_·_v}_v∈ V, 
  then one can obtain a cluster whose conductance is nearly as small as
  that guaranteed by Cheeger's inequality.
Such a statement does not hold for the rows in
   the original network data , particularly 
  when  is sparse.

In fact, the result of 
  Andersen, Chung, and Lang <cit.>
  is much stronger.
They showed that for any cluster S ⊂ V, 
  if one selects a random node v∈ S with probability
   proportional to the weighted degree d_v of the node, 
   then, with probability at least 1/2, 
   one can identify a cluster S' of conductance at most 
  O(√(_(S)log n)) by
  applying sweep to vector ^-1_·_v.
In other words, the row vectors in the PageRank completion — i.e., 
  the personalized PageRank vectors that 
  represent the individual data associated with nodes —
  have rich and direct information about network clustering 
  (measured by conductance).
This is a property that the original network data simply doesn't  have,
  as one is usually not able to  identify good clusters
  directly from the individual rows of .

In summary, Cheeger’s inequality 
  and its algorithmic proof can be viewed as the mathematical foundation 
  for global spectral partitioning, 
  because the Fiedler/Cheeger vectors are 
  formulated from the network data as a whole.
From this global perspective, both 
  the original network and its PageRank completion are equally effective.
In contrast, from the local perspective of individual-row data,
  Andersen, Chung, and Lang's result highlights the 
  effectiveness of the PageRank completion to
  local clustering <cit.>:
The row data associated with nodes in the PageRank completion 
  provides effective information for identifying good clusters.
Similarly, from the corresponding column in the PageRank completion,
  one can also directly and “locally” obtains
  each node's PageRank centrality.
In other words, PageRank completion transforms the input network data 
  into a “complete-information” network model , and 
  in the process, it distilled the centrality/clusterability information
   implicitly embedded globally in 
   into an ensemble of nodes' “individual” network data
   that explicitly encodes the centrality information and 
   locally capturing the clustering structures.



§ CONNECTING MULTIFACETED NETWORK DATA


The formulations highlighted in 
  Section <ref>,
   such as the cooperative, incentive, powerset, and preference models,
  are just a few examples of network models beyond the traditional
  graph-based framework.
Other extensions include the 
  popular probabilistic graphical model  <cit.> and
  game-theoretical graphical model <cit.>.
These models use relatively homogeneous node and edge types,
  but nevertheless represent a great source of expressions
  for multifaceted and multimodal network data.

While diverse network models enable us to express multifaceted network data,
  we need mathematical and algorithmic tools to connect them.
For some applications such as community identification, one may need to properly 
  use some data facets as metadata to evaluate or cross validate 
  the network solution(s) identified from the main network facets <cit.>.


But more broadly, for many real-world network analysis tasks, we need 
  a systematic approach to network composition
 whose task is to integrate the multifaceted data into a single effective
   network worldview.
Towards this goal, a basic theoretical step in multifaceted network analysis is 
  to establish a unified worldview for capturing 
  multifaceted network data expressed in various models.


Although fundamental, formulating a unified worldview 
  of network models is still largely an outstanding research problem.
In this section, 
  we sketch our preliminary studies in using Markov chains
  to build a “common platform” for the network models discussed 
  in Section <ref>. 
We hope this study will inspire a general theory for data 
  integration, network composition, and multifaceted network analysis.
We also hope that it will
   help to strengthen the connection between various fields,
  as diverse as statistical modeling, geometric embedding,
  social influence, network dynamics, game theory, and 
  social choice theory,
  as well as various application domains
  (protein-protein interaction, viral marketing,
  information propagation, electoral behavior,
  homeland security, healthcare, etc.),
  that have provided different but valuable techniques and
  motivations to network analysis.
  



 §.§ Centrality-Conforming Stochastic Matrices of Various Network Models



Markov chain — a basic statistical model — is also 
 a fundamental network concept.
For a weighted network G = (V,E,),
  the standard random-walk transition  
 (_^out)^-1· 
  is the most widely-used stochastic matrix associated with G.
Importantly, Section <ref> illustrates that
 other Markov chains
 — such as PageRank Markov chain _,α —
  are also natural with respect to network data .
Traditionally, a Markov chain is characterized by
  its stochastic condition, stationary distribution, mixing time, and
  detailed-balancedness.
Theorem <ref> highlights another
  important feature of Markov chains in the context of 
  network analysis: 
The PageRank Markov chain is conforming with respect to 
   PageRank centrality, that is, 
  for any network G = (V,E,) and α > 0, we have:

    _,α^T·1 = ,α.








How should we derive stochastic matrices from other network models?
Can we construct Markov chains that are
  centrality-confirming with respect to
  natural centrality measures of these network models?



In this section, 
  we will examine some centrality-confirming Markov chains that can be
  derived from network data given by 
  preference/incentive/cooperative/powerset  models.



  §.§.§ The Preference Model


For the preference model, there is a family of natural Markov
  chains, based on weighted 
  aggregations in social-choice theory <cit.>.
For a fixed n, let ∈ (ℝ^+∪{0})^n
  be a non-negative and monotonically non-increasing vector.
For the discussion below, we will assume that  is normalized 
  such that ∑_i=1^n [i] = 1.
For example, while the famous Borda count <cit.> 
  uses = [n,n-1,...,1]^T,
  the normalized Borda count uses = [n,n-1,...,1]^T/n  2.



Suppose A = (V,Π) is a preference network 
  over V = [n] and
   is non-negative and monotonically non-increasing weight vector,
  with ||||_1 = 1.
Let _A, be the matrix  in which for each u∈ V, the
  u^th row of _A, is: 

    π_u∘ = [[π_u(1)],...,(π_u(n))].

Then, _A,  defines a Markov chain, i.e.,
   _A,1 = 1.


_A, is a stochastic matrix
  because each row of _A, is a permutation of , 
  and permutations preserve the L1-norm of the vector.


Social-choice aggregation based on  also defines
  the following natural centrality measure, 
  which can be viewed as the collective ranking over V based on the
  preference profiles of A = (V,Π): 

    _Π,[v] = ∑_u∈ V[π_u(v)]


Like PageRank Markov chains, 
  weighted preference Markov chains
  also enjoy the centrality-conforming property:

For any preference network A=(V,Π), in which Π∈^|V|:

    _A,^T ·1 = _Π,





  §.§.§ The Incentive Model


We now focus on a special family of incentive networks:
We assume for  U = (V,u) and s∈ V:


  * u_s is monotonically non-decreasing, i.e., for all T_1⊂ T_2,
  u_s(T_1) ≤ u_s(T_2).

  * u_s is normalized, i.e., u_s(V∖{s}) = 1.


Each incentive network defines a natural cooperative network, 
  H_U = (V,τ_SocialUtility):
For  any S⊆ V, let the social utility
  of S be:

    τ_SocialUtility(S)  =  ∑_s∈ S u_s(S∖{s})


The Shapley value <cit.> — a classical game-theoretical 
  concept — 
  provides a natural centrality measure for cooperative networks.

Suppose τ is the characteristic 
  function of a cooperative game over V =[n].
Recall that   denotes the set of all permutations of V.
Let S_π, v denotes the set of players preceding v in a permutation π∈.
Then, the Shapley value ϕ_τ^Shapley[v]  of a player v∈ V is:

    ϕ_τ^Shapley[v] = π∼τ[S_π,v∪{v}] - 
      τ[S_π,v]



The Shapley value ϕ_τ^Shapley[v]  
  of player v∈ V  is
   the  expected marginal contribution of v 
   over the set preceding v  in a random permutation of the players.    
The Shapley value has many attractive properties, and 
 is widely considered to be the fairest measure of 
  a player's power index in a cooperative game.

We can use Shapley values to define both the stochastic matrix and 
  the centrality of incentive networks U.
Let _U be the Shapley value of the cooperative game
  defined by τ_SocialUtility.
Note that the incentive network U
  also defines |V| natural individual cooperative networks:
For each s∈ V and T⊂ V, let:

    τ_s(T)  =  
    {[ u_s(T∖{s})           ;          0            ].




Suppose U = (V,u) is an incentive network over V = [n],
 such that ∀ s∈ V,
 u_s is monotonically non-decreasing and u_s(V∖{s}) = 1.
Let _U be the matrix in which for each s∈ V, the
  s^th row of _U is the Shapley value of
  the cooperative game with characteristic function τ_s.
Then, _U defines a Markov chain and is centrality-conforming 
  with respect to _U, i.e., 
  (1) _U1 = 1 and (2) _U^T1 = _U.


This proposition is the direct consequence of two basic 
  properties of Shapley's beautiful characterization <cit.>:


  * The Shapley value  is efficient:  
    ∑_v∈ Vϕ_τ[v] = τ(V).

  * The Shapley value is  Linear: 
For any two characteristic functions τ and ω, 
ϕ_τ + ω = ϕ_τ + ϕ_ω.

By the assumption  u_s is monotonically non-decreasing,
  we can show that every entry of the Shapley value
  (as given by Eqn: (<ref>)) is non-negative.
Then, it follows from
   the efficiency of Shapley values and the assumption that
  ∀ s∈ V, u_s(V∖{s}) = 1,
  that _U is a stochastic matrix, and hence it
   defines a Markov chain.
Furthermore, we have:

    τ_SocialUtility = ∑_s∈ Vτ_s

Because _U is the Shapley value of the 
  cooperative game with characteristic function 
τ_SocialUtility,
  the linearity of the Shapley value then implies
  _U^T1 = _U, i.e., 
  _U is centrality-conforming with respect to _U.




  §.§.§ The Influence Model


Centrality-conforming Markov chain can also be
  naturally constructed for a family of powerset networks.
Recall from  Section <ref> that
  an influence process  and social network G=(V,E)
  together define a powerset network, 
 P_G,: 2^V× 2^V→ [0,1],
where for each T ∈ 2^V, 
 P_G,[S,T] 
 specifies the probability that T is the final activated set 
  when S cascades its influence through G.
As observed in <cit.>, the influence model also
  defines a natural cooperative game, whose
  characteristic function is the 
  influence spread function:

    σ_G,(S) = ∑_T⊆ V |T|·P_G,[S,T], 
      ∀ S⊆ V.

Chen and Teng <cit.> proposed to use the Shapley value 
  of this social-influence game as a centrality measure
  of the powerset network defined by  P_G,.
They showed that this social-influence centrality measure, to be denoted
  by _G,,
  can be uniquely characterized by a set of five natrual axioms <cit.>.
Motivated by the PageRank Markov chain, they also
  constructed the following centrality-conforming Markov chain
  for social-influence models.


Suppose G = (V,E) is a social network and 
  is a social-influence process.
Let _G, be the matrix in which for each v∈ V,
  the v^th row of _G,
  is given by the Shapley value
  of the cooperative game with the following 
  characteristic function:

    σ_G,,v(S) = ∑_T⊆ V[ v∈ T]·P_G,[S,T]

where [ v∈ T] is the indicator function for event (v∈ T).
Then, _G, defines a Markov chain and is 
  centrality-conforming with respect to _G,, 
  i.e., (1) _G,1 = 1 and (2) 
  _G,^T1 = _G,.


For all v∈ V, the characteristic function σ_G,,v
  satisfies the following two conditions:


  * σ_G,,v is monotonically non-decreasing.

  * σ_G,,v(V) = 1.

The rest of the proof is essentially the same as the 
   proof of Proposition <ref>.




 §.§ Networks Associated with Markov Chains


The common feature in the Markovian formulations 
  of Section <ref> 
  suggests the possibility of a general
  theory that various network models beyond graphs can be 
  succinctly analyzed through the worldview of Markov chains.
Such analyses are forms of dimension reduction of network data —
  the Markov chains
   derived, such as from social-influence instances, usually
   have lower dimensionality than the original network models.
In dimension reduction of data, inevitably some information is lost.
Thus, which Markov chain is formulated from a particular network model
  may largely depend on through which mathematical lens we are looking
  at the network data.
The Markovian formulations of Section <ref> are largely 
  based on centrality formulations.
Developing a more general Markovian formulation theory 
  of various network models remains the subject of future research.

But once we can reduce the network models specifying various aspects
  of network data 
  to a collection of Markov chains representing the corresponding 
  network facets, 
   we effectively reduce multifaceted network analysis 
  to a potentially simpler task — the analysis of multilayer networks
  <cit.>.
Thus, we can apply various emerging techniques for multilayer network analysis
<cit.> 
  and network composition <cit.>.
We can further use standard techniques
  to convert the  Markov chains into weighted graphs
  to examine these network 
  models through the popular graph-theoretical worldview.



  §.§.§ Random-Walk Connection


Because of the following characterization, the random-walk is 
  traditionally the most commonly-used connection
  between Markov chains and weighted networks.


For any directed network G = (V,E,) in which every node
  has at least one out-neighbor, there is a unique 
  transition matrix:

    _ = (_^out)^-1

   that captures the (unbiased) random-walk Markov process on G.
Conversely, given a transition matrix , 
  there is an infinite family of weighted networks 
  whose random-walk Markov chains are consistent with .
This family is given by:

    {: }.



The most commonly-used diagonal scaling is , the diagonal matrix
  of the stationary distribution.
This scaling is partially justified by the 
  fact that  is an undirected network
  if and only if   is a detailed-balanced Markov chain.
In fact in such a case,  is symmetric 
  if and only if there exists c> 0, = c·.
Let's call  the canonical Markovian network of  
  transition matrix  .
For a general Markov chain, we have:

    1  = π^T 1 = π

Thus, although canonical Markovian networks are usually directed,
  their nodes always have the same in-degree and out-degree.
Such graphs are also known as the weighted Eulerian graphs. 



  §.§.§ PageRank Connection


Recall that Theorem <ref> features
  the derivation of 
   PageRank-conforming Markov chains from weighted networks.










In fact, Theorem <ref> and its PageRank power series can be 
  naturally extended to any transition matrix :

For any finite irreducible and ergodic Markov chain 
    and restart constant α > 0,
  the matrix α∑_k=0^∞ (1-α)^k ·^k
  is a stochastic matrix that preserves the detailed-balancedness,
   the stationary distribution, and the spectra of .

Let's call  α∑_k=0^∞ (1-α)^k ·^k
  the canonical PageRank-Markovian network of transition matrix .

For any Markov chain , 
  the random-walk Markov chain of the 
  canonical PageRank-Markovian network
  α∑_k=0^∞ (1-α)^k ·^k
   is conforming with respect to the PageRank of
   the canonical Markovian network .




  §.§.§ Symmetrization


Algorithmically, computational/optimization problems on 
  directed graphs are usually harder than they are on undirected graphs.
For example, many recent breakthroughs in scalable graph-algorithm design
  are for limited to undirected graphs <cit.>.
To express Markov chains as undirect networks, we can 
  apply the following well-known
  Markavian symmetrization formulation.
Recall a matrix L is a Laplacian matrix
  if (1) L is a symmetric matrix with non-positive off-diagonal entries,
  and (2) L·1 = 0.


For any irreducible and ergodic finite Markov chain :

    -  + ^T/2

is a Laplacian matrix, where  the diagonal matrix
  associated with 's stationary distribution.
Therefore, + ^T/2 is a
  symmetric network, whose degrees are normalized to stationary distribution
π = ·1.
When  is detailed balanced, + ^T/2 is 
  the canonical Markovian network of .


We include a proof here for completeness.
Let  be the stationary distribution of .
Then:

    ^T     =    
    ·1     =    
    ·1     =    1

Therefore:

    ( -  + ^T/2)·1
    = ( - 1 + ^T/2)
    = 0

The Lemma then follows from the fact that
1/2( + ^T) is symmetric and non-negative.





Through the PageRank connection,
  Markov chains also have two extended Markovian symmetrizations:

For any irreducible and ergodic finite Markov chain  
  and restart constant α > 0, the two
matrices below:

    - α∑_k=0^∞ (1-α)^k ·^k + (^T)^k/2
     - 
    α∑_k=0^∞ (1-α)^k ·(^-1· + ^T/2)^k

are both Laplacian matrices. 
Moreover, 
  the second Laplacian matrix is 1/α-spectrally similar 
  to (1-α)·( -  + ^T/2).



















  §.§.§ Network Interpretations
 


We now return to Balcan et al.'s approach <cit.>
  for deriving preference networks from affinity networks.
Consider the following natural extension of linear orders
   to express rankings with ties:
An ordered partition of V is a total order of a partition 
  of V.
Let V denote the set of all  ordered partitions of V:
For a σ∈, for i,j∈ V, we 
i is ranked strictly ahead of j if i and j belong to
different partitions, and the partition containing i is ahead of the
partition containing j in σ.
If i and j are members of the same partition in σ, we say
  σ is indifferent of i and j.
 


 
Suppose G = (V,E,) is a weighted graph and 
  α >0 is a restart constant.
For each u ∈ V, let π_u be the ordered partition 
  according to the descending ranking of V 
  based on the personalized PageRank 
  vector _u = _,α[u,:].
We call Π_,α ={π_u}_u∈ V  
  the PageRank preference  profile of V with respect to G,
and A_,α = (V,Π_,α) the 
PageRank preference network of G.


As pointed out in <cit.>, other methods for deriving preference networks
  from weighted networks exist.
For example, one can obtain individual preference rankings
  by ordering nodes according to shortest path distances, 
  effective resistances, or maximum-flow/minimum-cut values.


 Is the PageRank preference a
  desirable personalized-preference profile
  of an affinity network?
 


This is a basic question in network analysis.
In fact, much work has been done.
I will refer readers to the beautiful axiomatic approach of 
Altman and Tennenholtz 
  for characterizing 
  personalized ranking systems <cit.>.
Although they mostly studied unweighted networks, many of their results can be
  extended to weighted networks.
Below, I will use Theorem <ref>
  to address the following question that I was asked when 
  first giving a talk about PageRank preferences.

By taking the ranking information from PageRank matrices —
  which is usually asymmetric — one may lose valuable network information.
For example, when G = (V,E,) is a undirected network,
 isn't it desirable to define ranking information according
  to  a symmetric matrix?



At the time, I was not prepared to answer this question and replied
  that it was an excellent point.
Theorem <ref> now provides an answer.
Markov chain theory uses an elegant concept to characterize
  whether or not a Markov chain  has an undirected network realization.
Although Markov-chain transition matrices are usually asymmetric,
  if a Markov chain is detailed-balanced,
  then its transition matrix  can be 
  diagonally scaled into a symmetric matrix by its stationary distribution.
Moreover, Π is the “unique” underlying undirected network
  associated with .
By Theorem <ref>, 
  _,α is a Markov transition matrix with 
  stationary distribution _, and thus,
  _α = _·_,α
  is symmetric if and only if  is symmetric.
Therefore, because the ranking given by _u is the same as the ranking 
  given by [u,:], the PageRank preference profile
  is indeed derived from a symmetric matrix when  is symmetric.

We can also define clusterability and other network models based on
  personalized PageRank matrices.
For example:


  * PageRank conductance:

    _(S) :=
    ∑_u∈ S,v∉S[u,v]/min(∑_u∈ S,v∈ V[u,v], ∑_u∉S,v∈ V[u,v])



  * PageRank utility:

    _(S) := ∑_u∈ S,v∈ S_,α[u,v]



  * PageRank clusterability:

    _(S) := _(S)/|S|


Each of these functions defines a cooperative network
    based on G = (V,E,).
These formulations are connected with the PageRank of G. 
For example,  the Shapley value of the cooperative network given by 
  τ = _ is the PageRank of G.

_,α can also be used to define incentive and powerset
  network models.
The former can be defined by 
  u_s(T) = ∑_v∈ T_,α[s,v],
   for s∈ V, T⊂ V and s∉T.
The latter can be defined by

θ_(S,T) = ∑_u∈ S,v∈ T_,α[u,v]/|S|

for S,T⊆ V. 
θ_(S,T) measures the rate of PageRank contribution
   from S to T.



 §.§ Multifaceted Approaches to Network Analysis: Some Basic Questions


We will now conclude this section with a few basic questions,
  aiming to study how structural concepts in one network model
  can inspire structural concepts in other network models. 
A broad view of network data
  will enable us to comprehensively examine 
  different facets of network data,
  as each network model brings out different aspects
  of network data.
For examples, 
  the metric model is based on geometry, 
   the preference model is inspired by  social-choice theory <cit.>, 
   the incentive and cooperative models are based on
   game-theoretical and economical principles 
  <cit.>,
  the powerset model  is motivated by social influences 
  <cit.>,
  while  the graphon <cit.> is based on graph limits and statistical
 modeling.
We hope that addressing questions below will help us to 
  gain comprehensive and comparative understanding of 
  these models and the network structures/aspects
    that these models may reveal.
We believe that multifaceted and multimodal approaches to network analysis
  will become increasingly more essential 
  for studying major subjects in network science.
  



  * How should we formulate  
  personalized centrality measures with respect
  to other commonly-used network centrality measures
  <cit.>?
Can they be used to define meaningful
   centrality-conforming Markov chains?

  * How should we define centrality measures and 
  personalized ranking systems
  for general incentive or powerset networks?
How should we define personalized Shapley 
  value for cooperative games?
How should we define weighted networks from cooperative/incentive/powerset
  models?


  * What are natural Markov chains associated with the probabilistic graphical models
<cit.>?
How should we define centrality and clusterability for 
  this important class of network models that 
  are central to statistical machine learning?


  * What constitutes a community in a probabilistic graphical model?
  What constitutes a community in a
   cooperative,  incentive, preference, and powerset network?
How should we capture network similarity 
  in these models?
How should we integrate them if they represents different facets of network data?


  * How should we evaluate different clusterability measures and their
  usefulness to community identification 
  or clustering? 
For example, PageRank conductance and PageRank clusterability are
  two different subset functions, but the latter applies to directed networks.
How should we define clusterability-conforming centrality
  or centrality-forming  clusterability?



  * What are limitations of Markovian worldview of various network models?
What are other unified worldview models for multifaceted network data?



  * What is the fundamental difference between “directed”
  and “undirected” networks in various models?
 



  * How should we model networks with non-homogeneous nodes and edge types?


More broadly, the objective is to build 
  a systematic algorithmic framework for understanding
  multifaceted network data, particular given that many natural network 
  models are highly theoretical in that their 
  complete-information profiles have exponential dimensionality
  in |V|.
In practice, they must be succinctly defined.
The algorithmic network framework consists of the complex and challenging
 tasks of integrating  sparse and 
  succinctly-represented multifaceted network data N = (V, F_1,...,F_k) 
  into an effective worldview (V,W) 
  based on which, one can effectively build succinctly-represented
  underlying models for network facets,
  analyzing the interplay between network facets, and 
  identify network solutions that are consistent
   with the comprehensive network data/models.
What is a general model 
  for specifying multifaceted network data?
How should we formulate the problem
  of network composition for multifaceted network data?




§ TO JIRKA


The sparsity, richness, and ubiquitousness
 of multifaceted networks data
 make them wonderful subjects
 for mathematical and algorithmic studies.
Network science has truly become a “universal discipline,” 
  with its multidisciplinary roots and  interdisciplinary presence.
However, it is a fundamental and conceptually challenging task to
  understand network data, due to the vast network phenomena.


The holy grail of network science is to understand 
 the network essence that underlies the observed 
sparse-and-multifaceted network data.



We need an analog of the concept of range space, which 
  provides a united worldview of a 
  family of diverse problems that are fundamental in statistical 
  machine learning, geometric approximation, and data analysis.
I wish that I had a chance to discuss with you about 
  the mathematics of networks — beyond just the geometry of graphs —
  and to learn from your  brilliant insights
  into  the essence of networks.
You and your mathematical depth and clarity will be greatly missed, Jirka.




abbrv

