∎

11institutetext: Suman Banerjee 22institutetext: Department of Computer
Science and Engineering
Indian Institute of Technology Jammu, India.
22email<EMAIL_ADDRESS>
# A Survey on Mining and Analysis of Uncertain Graphs ††thanks: The author is
supported by the Start Up Research Grant provided by Indian Institute of
Technology Jammu, India.

Suman Banerjee

(Received: date / Accepted: date)

###### Abstract

_Uncertain Graph_ (also known as _Probabilistic Graph_) is a generic model to
represent many real-world networks from social to biological. In recent times
analysis and mining of uncertain graphs have drawn significant attention from
the researchers of the data management community. Several noble problems have
been introduced and efficient methodologies have been developed to solve those
problems. Hence, there is a need to summarize the existing results on this
topic in a self-organized way. In this paper, we present a comprehensive
survey on uncertain graph mining focusing on mainly three aspects: (i)
different problems studied, (ii) computational challenges for solving those
problems, and (iii) proposed methodologies. Finally, we list out important
future research directions.

###### Keywords:

Uncertain Graph Reliability Clustering Classification Node Similarity
Rechability Query

##  1 Introduction

Graphs are often used to represent real-world networks, such as _social
networks_ (nodes represent users and edges represent social ties) Carrington
et al. Carrington et al. (2005), _transportation networks_ (nodes represent
cities and edges represent roads) Bell and Iida Bell and Iida (1997),
_protein-protein interaction networks_ (nodes represent proteins and edges
represent interaction relationship) Brohee and Van Helden Brohee and Van
Helden (2006) and so on. In many realistic applications, _uncertainty_ is
intrinsic in graph data due to many practical reasons, which includes noisy
measurement Aggarwal Aggarwal (2010), inferences and prediction error Adar and
Re Adar and Re (2007), explicit manipulation and so on. As an example, in case
of protein-protein interaction (PPI) networks, as high throughput interaction
detection methods are often erroneous, and hence interaction of two proteins
is probabilistic in nature. This kind of graphs are often called as uncertain
graphs or probabilistic graphs, where each edge of the network is associated
with a probability value. The interpretation of this probability may vary from
context to context. In case of PPI Network, the assigned probability to an
edge is basically its existential probability. On the other hand, in case of a
social network, the assigned probability to an edge may signify the
probability with which one can influence other Chen et al. Chen et al. (2013).
In a generic seance, an uncertain graph is basically a graph whose edges are
marked with a probability value. Due to the wider applicability of uncertain
graphs in different domains such as _social network analysis_ Kempe et al.
Kempe et al. (2003), _computational biology_ Zhao et al. Zhao et al. (2014),
_crowed sourcing_ Ke et al. (2018); Yalavarthi et al. (2017b, a), _recommender
systems_ Taranto et al. (2012), _wireless networks_ Coon et al. (2018)
analysis of mining of such networks become key research area in recent times.

Extensive studies on uncertain graphs lead to many interesting problems Khan
et al. (2018b); Kassiano et al. (2016), which includes _frequent pattern
matching_ Yuan et al. (2016); Chen et al. (2018), _subhraph extraction_ Chen
and Wang (2010); Yuan et al. (2011a), _clustering of uncertain graphs_
Ceccarello et al. (2017a); Han et al. (2019), _motif counting_ Ma et al.
(2020), _reliability computation_ Khan et al. (2018a) and many more. Also,
over the years several solution methodologies have been developed. So there is
a need to organize the existing results in a self contained manner. In this
paper, we serve this purpose by surveying the existing literature. First, we
report the goals of this survey.

###  1.1 Focus and Goal of the Survey

In this survey, the main focus are three folded and they are listed below:

  * •

Different problems studies on uncertain graph mining and analysis,

  * •

Major challenges for solving these problems,

  * •

Proposed solution methodologies.

The goal of the survey are as follows:

  * •

to provide a comprehensive background on uncertain graph mining and different
problems introduced and studied in this domain.

  * •

to propose a taxonomy for classifying the existing literature and brief it in
a concise manner.

  * •

to summarize the existing literature and points out future research
directions.

###  1.2 Proposed Taxonomy

Broadly, the problems that have been studied in uncertain graph mining domain
can be classified into three main categories: (i) Computational Problems (e.g.
computation of $u-v$ reliability, clustering etc.), (ii) Querying Problems
(e.g., reachability queries , queries regarding the existence of a particular
combinatorial structures etc.), and (iii) Graph Algorithmic Problems (e.g.,
construction of spanning tree, link prediction, information flow maximization
etc.). Also, there are some problems such as _sparsification_ , _node
classification_ etc. which does not come under any of the three heads, and we
put them under miscellaneous problems. Figure 1 gives a diagrammatic view for
the proposed classification of the existing literature on uncertain graph
mining.

Figure 1: Taxonomy for classifying the existing literature.

###  1.3 Organization of the Survey

Rest of the paper is organized as follows: Section 2 lists required
preliminary definitions. Section 3 describes different problems studied on
uncertain graph mining. In Section 4, we report the existing challenges for
solving the problems. Existing solution methodologies for these problems are
described in Section 5. In Section 6, after analyzing the existing literature
we describe the current research trends and point out existing research gaps.
Section 7 list out existing future research directions. Finally, Section 8
concludes the survey.

##  2 Preliminaries

In this section, we describe required preliminary concepts. Initially, we
start with the uncertain graph.

######  Definition 1 (Uncertain Graph)

111Please don’t confuse between uncertain graph and random graph Bollobás and
Béla (2001). Uncertain graph and probabilistic graph are same, however, random
graph is completely different and noting to do in this paper. Hence, we have
not defined it in this paper.

An uncertain graph is denoted as $G(V,E,P)$, where
$V(G)=\\{v_{1},v_{2},\ldots,v_{n}\\}$ denotes the set of vertices,
$E(G)=\\{e_{1},e_{2},\ldots,e_{m}\\}$ denotes the set of edges, and $P$ is the
edge weight function that assigns each edge to its probability, i.e.,
$P:E(G)\longrightarrow(0,1]$.

If the uncertain graph is weighted, along with $V$, $E$, and $P$, there is
also an edge weight function $W$ that assigns each edge to a real number,
i.e., $W:E(G)\longrightarrow\mathbb{R}$. We denote the number of vertices and
edges of $G$ as $n$ and $m$, respectively. Depending upon the situation, an
uncertain graph may be directed or undirected. As in most of the existing
studies, the considered uncertain graph is undirected, in this paper also
unless otherwise stated by uncertain graph we mean it is undirected. Also, in
some situations instead of single probability value, there may be multiple
values associated with an edge. Take the example of a social network, where
probability associated with each edge is basically the influence probability
between two users. Now, influence probability may vary from context to context
Chen et al. (2016b). This means a sportsman can influence his friends and
followers regarding any news related to sports with higher probability
compared to the others. Let, $C=\\{c_{1},c_{2},\ldots,c_{k}\\}$ be the set of
$k$ different contexts. In this case the social network can be modeled as an
uncertain graph, where each edge of the network is associated with $k$ number
of probability values. In that case, the probability function can be defined
as $P:E\times C\longrightarrow(0,1]$. Standered graph theoretic terminologies
such _degree_ , _neighborhood_ , _path_ , _subgraph_ , _subgraph isomorphism_
, _spanning tree_ etc. with their definitions and notations have been adopted
from Diestel (2012) and not described here. For any arbitrary edge $e\in
E(G)$, $P(e)$ denotes the probability associated with the edge $e$. _Possible
World Semantic_ is widely used to represent to an uncertain graph as a
probability distribution over a set of deterministic graphs, which is defined
next.

######  Definition 2 (Possible World Semantic)

By this model, an uncertain graph is represented as a probability distribution
over $2^{m}$ number of deterministic graphs by keeping an edge with
probability $P(e)$ and removing it with probability $(1-P(e))$. Hence, given
an uncertain graph $G(V,E,P)$, the probability that the deterministic graph
$\mathcal{G}(V,\mathcal{E})$ (Here, $V(G)=V(\mathcal{G})$, and
$E(\mathcal{G})\subseteq E(G)$) will be generated can be computed by the
following equation:

$P_{\mathcal{G}\sqsubseteq G}=\underset{e\in
E(\mathcal{G})}{\prod}P(e)\underset{e\in E(G)\setminus
E(\mathcal{G})}{\prod}(1-P(e))$ (1)

Figure 2 shows an example of an uncertain graphs with its possible world. In
the example $|E(G)|=3$, hence $2^{3}=8$ deterministic graphs will be in the
possible world of $G$.

Figure 2: A toy example of an uncertain graph with its possible world

Given a graph and two of its vertices distance between them is defined as the
length of the shortest path. However, in case of uncertain graphs distance
between two vertices can be defined in many ways, which is stated next.

######  Definition 3 (Distance in Uncertain Graphs)

Potamias et al. (2009) Given an uncertain graph $G(V,E,P)$, and two of its
vertices $u,v\in V(G)$, there are four different distance measure available in
the literature:

  * •

Majority Distance: It is defined as the most probable shortest path distance
between $u$ and $v$.

  * •

Expected Distance: It is defined as the expected shortest path distance
between $u$ and $v$ among all the possible world graphs.

  * •

Expected Reliable Distance: It is defined as the expected shortest path
distance between $u$ and $v$ among all the possible world graphs in which $u$
and $v$ are connected.

  * •

Median Distance: It is defined as the median shortest path distance among all
the possible world graphs.

Mathematical expressions for computing these distance measures are given in
Table 1. Here, $P_{uv}(d)$ denotes the probability that the distance between
$u$ and $v$ is $d$.

Distance Metric | Mathematical Expression
---|---
Majority Distance | $dist_{MD}=\underset{d}{argmax}P_{uv}(d)$
Expected Distance | $dist_{ED}=\underset{d}{\sum}d.P_{uv}(d)$
Expected Reliable Distance | $dist_{ERD}=\underset{d|d<\infty}{\sum}d\frac{P_{uv}(d)}{1-P_{uv}(d)}$
Median Distance | $dist_{MD}=\underset{D}{argmax}\\{\sum_{d=0}^{D}P_{uv}(d)<\frac{1}{2}\\}$
Table 1: Different distance measures in uncertain graphs.

In a deterministic graph, two vertices are always reachable from each other if
they belong to the same connected component. However, in case of uncertain
graphs, reachability between two vertices are always probabilistic, which is
called as _reliability_ and it is defined next.

######  Definition 4 ($u-v$ Reliability)

Given an uncertain graph $G(V,E,P)$, and two vertices $u,v\in V(G)$, let
$I_{\mathcal{G}}(u,v)$ be the indicator boolean variable which takes the value
$1$ if $u$ and $v$ are reachable from each other in the deterministic graph
$\mathcal{G}$, otherwise it is $0$. Now, reliability between $u$ and $v$ is
basically the expected value of rechability, which can be given by the
Equation 2

$R(u,v)=\underset{\mathcal{G}\sqsubseteq
G}{\sum}I_{\mathcal{G}}(u,v).P_{\mathcal{G}\sqsubseteq G}$ (2)

Now, the notion of $u-v$ reliability for a uncertain graph can be extended for
a subset of the vertices (called as terminal vertices) which is stated in
Definition 5.

######  Definition 5 (Network Reliability)

For a given uncertain graph $G(V,E,P)$, and a set of terminal vertices
$\mathcal{T}\subseteq V(G)$, the network reliability is defined as the
probability that the graph induced by the vertex set $\mathcal{T}$ is
connected in $G$. This can be computed by Equation 3. Here,
$I(\mathcal{G},\mathcal{T})$ is a indicator variable whose value is $1$ when
$\mathcal{T}$ is connected and $0$ otherwise.

$R(G,\mathcal{T})=\underset{\mathcal{G}\in
L(G)}{\sum}I(\mathcal{G},\mathcal{T}).P_{\mathcal{G}\sqsubseteq G}$ (3)

Subsequently, the notion of $u-v$ reliability has been generalized by Khan et
al. Khan et al. (2018a) when the uncertain graph has more than one probability
value in every edge and this is defined next.

######  Definition 6 (Conditional $u-v$ Reliability)

Khan et al. (2018a) Let, $G(V,E,P)$ be an uncertain graph, and
$C=\\{c_{1},c_{2},\ldots,c_{k}\\}$ be the $k$ different contexts. Here, $P$ is
defined as $P:E\times C\longrightarrow(0,1]$. Now, for any given
$C_{1}\subseteq C$ and with the assumption that the contexts are independently
aggregated, the effective probability for any edge $e\in E(G)$ can be computed
by the Equation 4.

$P(e|C_{1})=1-\underset{c\in C_{1}}{\prod}(1-P(e|c))$ (4)

Similarly, by considering the contexts $C_{1}$, the probability that the
deterministic graph $\mathcal{G}$ will be generated can be computed by the
Equation 6.

$P(\mathcal{G}|C_{1})=\underset{e\in
E(\mathcal{G})}{\prod}P(e|C_{1})\underset{e\in E(G)\setminus
E(\mathcal{G})}{\prod}(1-P(e|C_{1}))$ (5)

Now, given two vertices $u,v\in V(G)$, and given the set of contexts $C_{1}$
the conditional reliability between $u$ and $v$ can be defined by Equation 6.

$R((u,v)|C_{1})=\underset{\mathcal{G}\sqsubseteq
G|C_{1}}{\sum}I_{\mathcal{G}}(u,v).P(\mathcal{G}|C_{1})$ (6)

Here, $I_{\mathcal{G}}(u,v)$ is an indicator variable whose value is $1$ if
$u$ and $v$ is connected in $\mathcal{G}$.

Given two deterministic graphs $\mathcal{G}$ and $\mathcal{H}$, a well known
computational task is to determine whether $\mathcal{G}$ contains a subgraph
isomorphic to $\mathcal{H}$. This is the popular _subgraph isomorphism
problem_ Lee et al. (2012) which is known to be NP-Complete Lewis (1983).
However, this problem can be translated in case of uncertain graphs by
incorporating the concept of _support_ , which is defined next.

######  Definition 7 (Support)

Given an uncertain graph $G(V,E,P)$, and a subgraph $S$, the support of $S$ is
defined as the fraction of the possible worlds that contains $S$ as subgraph.
Mathematically, this can be expressed as follows:

$sup(S;G)=\frac{|\mathcal{G}\in L(G):S\sqsubseteq\mathcal{G}|}{2^{m}}$ (7)

Now, given a support value $\alpha\in(0,1)$, an uncertain graph $G(V,E,P)$ and
a deterministic graph $\mathcal{G}(V,E^{{}^{\prime}})$, one immediate question
is that: “Does the uncertain graph $G$ contains the $G$ as a subgraph with
support greater than or equal to $\alpha$?” This kind of querying problems are
called structural pattern-based queries. Section 3.1 discusses it in more
details.

For a given graph, computation of _node similarity_ (how similar two nodes
are?) remains a central question in graph mining. Among many, one of the
popularly adopted node similarity measure is _Simrank_ initially proposed by
Jeh and Widom Jeh and Widom (2002). The intuition behind this similarity
measure is that two vertices are similar if they are referenced by similar
vertices.

######  Definition 8 (Simrank)

Given a deterministic graph $\mathcal{G}(V,E)$, and two vertices $u,v\in
V(\mathcal{G})$, the Simrank score between these two vertices are given by the
following equation:

$\sigma(u,v)=\begin{cases}1,&\text{if }u=v\\\
\frac{c}{|N^{in}(u)|.|N^{in}(v)|}\underset{w\in
N^{in}(u)}{\sum}\underset{w^{{}^{\prime}}\in
N^{in}(v)}{\sum}\sigma(w,w^{{}^{\prime}}),&\text{if }u\neq v\end{cases}$

where $N^{in}(u)$, and $N^{in}(v)$ denotes the set of incoming neighbors of
the nodes $u$ and $v$, respectively. $c\in(0,1)$ is the decaying factor whose
value is chosen as 0.8 Li et al. (2010a). Section 5.1.2 summarizes the
existing literature for simrank computation on uncertain graphs.

######  Definition 9 (Random Walk on Graphs)

Göbel and Jagers (1974) This is a discrete time process defined on graphs and
also it is one kind of graph search technique. Suppose, at time $t=0$ an
object is placed on the vertex $v$ of an undirected graph $\mathcal{G}(V,E)$.
At every discrete time steps $t=1,2,\ldots$ the object must move from one
vertex to one of its neighboring one. So, if the object is on the vertex
$v_{i}$ at time $t$, then the probability that the object will be on the
vertex $v_{j}$ at time $t+1$ is given by the following equation.

$m_{ij}=\begin{cases}\frac{1}{deg(v_{i})},&\text{if }(v_{i}v_{j})\in
E(\mathcal{G})\\\ 0,&\text{if }(v_{i}v_{j})\notin E(\mathcal{G})\end{cases}$

This probability values are reported as a $n\times n$ matrix $M$.

Existing solution methodologies for the simrank computation on uncertain
graphs use random walk concept as described in Section 5.1.2. Table 2
describes the notations and symbols with their interpretations used in this
paper. Many of the symbols have not been introduced yet and done as and when
needed.

Table 2: Notations used in this study Notation | Meaning
---|---
$G(V,E,P)$ | An uncertain graph
$G(V,E,P,W)$ | A weighted uncertain graph
$V(G),E(G)$ | Vertex set and edge set of $G$
$n,m$ | The size of the vertex set and edge set of $G$
$d$ | Diameter of $G$
$P$ | Edge weight function, i.e., $P:E(G)\longrightarrow(0,1]$
$W$ | Edge weight function, $W:E(G)\longrightarrow\mathbb{R}^{+}$
$A$ | Adjacency matrix of $G$
$u,v$ | Any two arbitrary vertices of $V(G)$
$N^{in}(u)$ | Set of incoming neighbors of $u$
$e/(uv)$ | An arbitrary edge from $E(G)$
$P(e)/P(uv)$ | Edge probability of the edge $e=(uv)$
$L(G)$ | Possible world set of $G$
$P_{\mathcal{G}\sqsubseteq G}$ | Generation probability of $\mathcal{G}$ from $G$
$\mathcal{G}(V,\mathcal{E})$ | A deterministic graphs from $L(G)$
$\sigma(u,v)$ | Simrank between $u$ and $v$ in $G$
$\mathcal{T}$ | Set of terminal vertices from $V(G)$
$\eta$ | Reachability / Reliability threshold
$C$ | Set of different contexts/ tags
$P(e|c)$ | The edge probability of the edge $e$ for the tag $c$
$C_{1}$ | A subset of contexts $C_{1}\subseteq C$
$P(e|C_{1})$ | Edge probability of $e$ after the aggregating the tags in $C_{1}$
$R((s,t)|C_{1})$ | Reliability between $s$ and $t$ for the tags in $C_{1}$
$D_{\beta}(u,v)$ | Distance between $u$ and $v$ in $G$ under distance measure $\beta$
$sup(S;G)$ | Support of $S$ on $G$
$\alpha$ | Specification Ratio
$S$ | The Simrank matrix
$q$ | An $s-t$ query
$G(q)$ | Uncertain graph corresponding to the $s-t$ query $q$
$g$ | Query Subgraph
$k$ | The set $\\{1,2,\ldots,k\\}$

##  3 Problems Studied on Uncertain Graphs

In these section, we describe the problems that have been studied in the
domain of uncertain graph mining. We devote one subsection to each categories
of sub-problems as shown in Figure 1.

###  3.1 Querying Uncertain Graphs

Different kinds of querying problems have been studied in the context of
uncertain graph such as _k -Nearest Neighbor Queries_ (kNN Queries),
_Reliability Queries_ , _Queries for Structural Pattern_ and so on. We
describe them one by one.

####  3.1.1 Reliability-Based Queries

Analysis of network reliability is old still active research area Ball (1986);
Brecht and Colbourn (1988); Ball et al. (1995); Khan et al. (2014); Guo and
Jerrum (2019). Given an uncertain graph $G(V,E,P,W)$, a probability threshold
$\eta\in(0,1)$, and a set of source nodes $S\subset V(G)$, _Reliability -Based
Query Problem_ asks to return $T\subseteq V(G)\setminus S$, such that the
probability of reachability from the set $S$ to $u$, $\forall u\in T$ is more
than $\eta$ Khan et al. (2014). From the computational point of view, the
problem can be posed as follows:

Reliability-Based Query Problem Input: Uncertain Graph $G(V,E,P,W)$, a vertex
subset $S\subset V(G)$, and probability threshold $\eta$. Question: Return the
set $T\subseteq V(G)\setminus S$, such that $\forall u\in T$,
$P(S,u)\geq\eta$.

####  3.1.2 Conditional Reliability Maximization Queries

Recently, Khan et al. Khan et al. (2018a) studied the conditional reliability
maximization problem. In case of single source single terminal variant of this
problem along with an uncertain graph $G(V,E,P)$ , and set of different
contexts $C=\\{c_{1},c_{2},\ldots,c_{k}\\}$ with $P:E(G)\times
C\longrightarrow(0,1]$, two specified vertices $s,t\in V(G)$, and a positive
integer $\ell\leq k$, this problem asks to choose subset of the contexts
$C^{{}^{\prime}}\subseteq C$ such that $|C^{{}^{\prime}}|=\ell$ such that
conditional $u-v$ reliability $R((s,t)|C^{{}^{\prime}})$ as described in
Definition 6 gets maximized. Mathematically, this problem can be expressed by
the following equation.

$C^{*}=\underset{C^{{}^{\prime}}\subseteq
C;|C^{{}^{\prime}}|=\ell}{argmax}R((s,t)|C^{{}^{\prime}})$ (8)

From the computational perspective, this problem can be posed as follows:

Conditional Reliability Maximization Queries Input: Uncertain Graph
$G(V,E,P)$, Set of Contexts $C=\\{c_{1},c_{2},\ldots,c_{k}\\}$. with
$P:E(G)\times C\longrightarrow(0,1]$, Two Vertices $s,t\in V(G)$, and a
Positive Integer $\ell\leq k$. Question: Return $C^{{}^{\prime}}\subseteq C$,
such that $|C^{{}^{\prime}}|=\ell$ and $R((u,v)|C^{{}^{\prime}})$ quantity is
maximized.

####  3.1.3 Nearest Neighbor(NN) Queries

This is a very generic data mining task, where given a set of data points and
a specific one of them (say $d$) the question is to return $k$ most similar
data points as $d$ from the remaining Roussopoulos et al. (1995). This problem
has also been studied extensively in graph data as well Malkov et al. (2014).
Recently, the $k$-NN Query Problem has been studied on uncertain graph as well
Potamias et al. (2010). Given a weighted uncertain graph $G(V,E,P,W)$, a
specific vertex $v\in V(G)$, a probabilistic distance function $D_{P}$ (anyone
of four as shown in Table 1), and a positive integer $k$, the _kNN Query on
Uncertain Graph_ Problem asks to return the set
$\\{u_{1},u_{2},\ldots,u_{k}\\}\subseteq V(G)\setminus\\{v\\}$ such that for
any vertex in $w\in V(G)\setminus\\{v,u_{1},u_{2},\ldots,u_{k}\\}$,
$D_{P}(v,w)\geq D_{P}(v,u_{i})$ for any $i\in[k]$. From the computational
perspective, the problem can be posed as follows:

$k$-NN Query on Uncertain Graph Problem Input: Weighted Uncertain Graph
$G(V,E,P,W)$, a specific vertex $v\in V(G)$, a probabilistic distance function
$D_{P}$, and $k\in\mathbb{Z}^{+}$. Question: Return the vertex set
$\\{u_{1},u_{2},\ldots,u_{k}\\}\subseteq V(G)\setminus\\{v\\}$ such that for
any vertex in $w\in V(G)\setminus\\{v,u_{1},u_{2},\ldots,u_{k}\\}$,
$D_{P}(v,w)\geq D_{P}(v,u_{i})$ for any $i\in[k]$.

This problem can also be defined on unweighted uncertain graph as well. In
that case $\forall e\in E(G)$, $W(e)=1$. Here, we have described the weighted
version only.

####  3.1.4 Structural Pattern-Based Queries

Finding or counting a given structure (also known as query graph) in a graph
database is a fundamental graph mining task Yan et al. (2005); Kuramochi and
Karypis (2005). This problem has also been studied in the context of uncertain
graph as well. Particularly, the structure that has been studied extensively
is the _frequent subgraph_ Zou et al. (2010a); Li et al. (2012), densest
subgraph Zou (2013), _Clique_ Mukherjee et al. (2015, 2017); Zou et al.
(2010b) etc.

Reliability-Based Query Problem Input: Uncertain Graph $G(V,E,P)$, a structure
$X$, and a probability threshold $\alpha$. Question: Is there a pattern $X$
whose support value is greater than or equal to $\alpha$.

Here, $X$ may be a $k$-clique, $k$-truss and many more.

###  3.2 Computation on Uncertain Graphs

Different computational problems have been studied in the context of uncertain
graphs. Here, we list them one by one.

####  3.2.1 $u-v$ Reliability Computation:

Given an uncertain graph $G(V,E,P)$, and two vertices $u$ and $v$, this
problem asks to compute the probability that $v$ is reachable from $u$. It can
be considered as the fundamental rechability problem in uncertain graph
context. From the computational perspective, the problem can be list as
follows:

$u-v$ Reliability Computation Input: An Uncertain Graph $G(V,E,P)$, two
specific vertices $u,v\in V(G)$. Task: Compute the reliability between $u$ and
$v$, i.e., $R(u,v)$ in $G$.

A variant of this problem has been introduced by Jin et al.Jin et al. (2011b),
where along with $G(V,E,P)$, $u,v\in V(G)$, we are also given with a distance
$d$ and the question is that what is the probability that $u$ is connected
with $v$ within the distance $d$.

####  3.2.2 $k$-Terminal Reliability Computation:

This is a more generalized version of the $u\mbox{-}v$ reliability computation
problem. In this problem, we are given with a uncertain graph $G(V,E,P)$ and a
set of $k$ terminal vertices $\mathcal{T}$, the network reliability
$R(G,\mathcal{T})$ can be given by the following equation:

$R(G,\mathcal{T})=\underset{\mathcal{G}\in
L(G)}{\sum}I(\mathcal{G},\mathcal{T}).P_{\mathcal{G}\sqsubseteq G}$ (9)

where $I(\mathcal{G},\mathcal{T})$ is a indicator variable whose value will be
$1$, if the vertices in $\mathcal{T}$ are connected in $\mathcal{G}$ and $0$
otherwise. This problem assks to compute the quantity $R(G,T)$ Sasaki et al.
(2019). From the computational point of view, this problem can be posed as
follows:

Network Reliability Computation: Input: An Uncertain Graph $G(V,E,P)$, a
subset of vertices $\mathcal{T}$. Task: Compute the network reliability
$R(\mathcal{T},G)$ in $G$.

####  3.2.3 Simrank Computation:

Simrank is a popular similarity measure between any two vertices of a graph
due to its applications in different problems including entity resolution Li
et al. (2010b); Yin et al. (2007), similar protein identification Whalen et
al. (2015) and so on. Recently, Simrank computation problem has also been
studied for uncertain graph as well Du et al. (2015); Zhu et al. (2016a,
2017). For a given uncertain graph $G(V,E,P)$, this problem asks to compute a
$n\times n$ similarity matrix $S_{sim}$, where the $(i,j)$-th entry contains
the SimRank similarity value. Computationally, the problem looks like the
following:

Simrank Computation on Uncertain Graphs: Input: An Uncertain Graph $G(V,E,P)$,
a subset of vertices $\mathcal{T}$. Task: Compute the network reliability
$R(\mathcal{T},G)$ in $G$.

####  3.2.4 Clustering of Uncertain Graphs

Clustring is a very generic data mining task. Given a set of data points this
problem asks to partition them into a number (may be given or may be dataset
dependent) of partitions (may be overlapping) such that data points belongs to
the same partitions should be similar in some sence and data points belongs to
the different partition should be different Jain et al. (1999). Clustring has
also been stuided extensively on graph data Aggarwal and Wang (2010). This
problem has also been studied in the context of uncertain graph as well Liu et
al. (2012); Han et al. (2019). The problem can be summarized as follows:

Clustering of Uncertain Graph Input: An Uncertain Graph $G(V,E,P)$, and the
number of clusters $K$. Task: Partition $V(G)$ into $C_{1}$, $C_{2}$,
$\ldots$, $C_{K}$ based on certain similarity measure.

###  3.3 Graph Algorithmic Problems

####  3.3.1 Spanning Tree Problem:

Given a weighted graph, computing the minimum cost spanning tree is classic
problem in Graph Algorithms Cormen et al. (2009). This problem has been
studied when the edge weights are uncertain Megow et al. (2017); Erlebach et
al. (2008). Recently, this problem has also been studied in the context of
uncertain graphs, where the weight of the edge is fixed, however there is a
probability of exsistence associated with every edge Zhang et al. (2016). From
the computational perspective, this problem can be posed as follows:

Most Reliable Spanning Tree Problem on Uncertain Graphs Input: An Weighted
Uncertain Graph $G(V,E,P,W)$. Task: Compute the minimum cost spanning tree
having the highest probability.

####  3.3.2 Link Prediction Problem:

Link prediction is a classic graph mining task, where the snapshot of the
network in different times, say $t=0,1,\ldots,T$, i.e., $G_{0}$, $G_{1}$,
$\ldots$, $G_{T}$ is given and the task is to predict the network snapshot at
time $T+1$, i.e., $G_{T+1}$ Zhang and Zaïane (2019). This problem has lot of
applications in social network analysis Liben-Nowell and Kleinberg (2007),
recommerder systems Li and Chen (2009) and so on. Recently, this problem has
has been studied considering the edge uncertainty Ahmed and Chen (2016);
Martínez et al. (2017). From the the computational point of view, this problem
can be posed as follows:

Link Prediction Problem on Uncertain Graphs Input: Snapshots of an Uncertain
Graph $G_{t}(V,E_{t},P_{t})$, $\forall t\in[T]$. Task: Output a $n\times n$
similarity matrix, where its $(i,j)$-th denotes the likelihood of
$(v_{i}v_{j})\in E(G_{T+1})$.

####  3.3.3 Information Flow Maximization Problem:

Network flow is a classic problem in network algorithms, where given a
directed graph with each edge is marked with its capasity and a source and
target vertex, the goal here is to decide how much flow need to pass through
each of the links such that total flow from the source to the target vertex is
maximized Ahuja et al. (1988). Recently, this problem has been studied in the
uncertain graph as well, however in a different setting Frey et al. (2017,
2018). Here the problem is defined as follows: Given a vertex weighted
uncertain graph $G(V,E,P)$, a query vertex $Q\in V(G)$, and a positive integer
$k$, this problem asks to find out the subgraph $\mathcal{G}$ that can contain
at most $k$ edges that maximizes the expected information flow towards $Q$.
From the computational point of view, this problem can be posed as follows:

Information Flow Maximization Problem on Uncertain Graph Input: A Vertex
Weighted Uncertain Graph $G(V,E,P,W)$, a query vertex $Q\in V(G)$, a positive
integer $k$. Task: Output a $n\times n$ similarity matrix, where its
$(i,j)$-th denotes the likelihood of $(v_{i}v_{j})\in E(G_{T+1})$.

###  3.4 Other Problems

####  3.4.1 Uncertain Graph Sparsification

Due to gigantic size of real-world networks, storing the entire network
requires huge storage cost and more importantly querying the entire graph
requires huge computational time. The remedy of this problem is not to store
the entire graph. One approach is to resolve this issue is that instead of
storing all the edges, store a subset of them. This leads to the problem of
graph sparsification. Here, the problem is to decide which edges to store such
that some specific property of the graph will not change much in the
sparcified graph Fung et al. (2019); Spielman and Srivastava (2011). Several
graph sparcification techniques have been proposed in the literature, such as
sparner-based sparscifier Peleg and Schäffer (1989), cut-based sparcifier Fung
et al. (2019) and many more. Recently, cut-based uncertain graph
sparsification problem has been studied by Parchas et al. Parchas et al.
(2018). Now, this problem has been formalized as follows: Given an uncertain
graph $G(V,E,P)$, and a vertex subset $S\subseteq V(G)$, the expected cut size
is defined by Equation 10.

$C_{G}(S)=\underset{\begin{subarray}{c}e=(uv)\in E(G)\\\ u\in S,v\in
V(G)\setminus S\end{subarray}}{\sum}P(e)$ (10)

Now, the _Absolute Discrepancy_ ($\delta_{A}(S)$) and _Relative Discrepancy_
($\delta_{R}(S)$) for the uncertain graph $G(V,E,P)$ with respect to the
sparcified uncertain graph
$G^{{}^{\prime}}(V,E^{{}^{\prime}},P^{{}^{\prime}})$ is defined in Equation 11
and 12, respectively.

$\delta_{A}(S)=C_{G}(S)-C_{G^{{}^{\prime}}}(S)$ (11)

$\delta_{A}(R)=\frac{C_{G}(S)-C_{G^{{}^{\prime}}}(S)}{C_{G}(S)}$ (12)

For a positive integer $k$, the discrepancy of the sparcified uncertain graph
$G^{{}^{\prime}}$ is defined as the sum of the absolute values discrepancy
values for all $k$ sized subsets.

$\Delta_{k}(G^{{}^{\prime}})=\underset{S\subseteq
V(G),|S|=k}{\sum}|\delta_{A}(S)|$ (13)

Now, for a given uncertain graph $G(V,E,P)$, a positive integer $k$, and a
sparsification ratio $\alpha\in(0,1)$, the uncertain graph sparsification
problem asks to to construct another uncertain graph
$G^{{}^{\prime}}(V,E^{{}^{\prime}},P^{{}^{\prime}})$ such that
$|E(G^{{}^{\prime}})|=\alpha|E(G)|$ that minimizes the sum of the
discrepancies $\underset{i\in[k]}{\sum}\Delta_{i}(G^{{}^{\prime}})$. From the
computational point of view, this problem can be posed as follows:

Uncertain Graph Sparsification Problem Input: An Uncertain Graph $G(V,E,P)$, a
positive integer $k$, a sparsification ratio $\alpha\in(0,1)$. Task: Construct
another uncertain graph $G^{{}^{\prime}}(V,E^{{}^{\prime}},P^{{}^{\prime}})$
such that $|E(G^{{}^{\prime}})|=\alpha|E(G)|$ to minimize
$\underset{i\in[k]}{\sum}\Delta_{i}(G^{{}^{\prime}})$.

####  3.4.2 Node Classification in Uncertain Graphs

The problem of classifying the nodes of a network has been studied extensively
Bhagat et al. (2011). Recently, this problem has also been studied in the
context of uncertain graphs as well Dallachiesa et al. (2014); Kong et al.
(2013); Han et al. (2015). This problem can be posed as follows: Given an
uncertain graph $G(V,E,P)$, a set of labels $T_{0}$ and subset of its vertices
$S\subset V(G)$ are labeled with a labeling function $L:S\longrightarrow
T_{0}$, predict the labels of the nodes in $V(G)\setminus S$. Computationally,
this problem can be posed as follows:

Node Classification in Uncertain Graphs Input: An uncertain graph $G(V,E,P)$,
label set $T_{0}$, a subset of vertices $S\subset V(G)$ with labeling function
$L:S\longrightarrow T_{0}$. Task: Predict the labels of the nodes in
$V(G)\setminus S$.

There are several other problems that have been studied such as uncertain
graph visualization Schulz et al. (2016); Sharara et al. (2011) etc. As the
intended audience of this paper is the researchers of the data mining and data
management community, hence we are not focusing on these problems. Also, it is
important to note that the problems that have been studied on uncertain graphs
may be classified in other way also. However, in our classification, the goal
was to put the problems that are of similar kind under the same umbrella.
Next, we proceed to describe the major challenges for solving these problems.

##  4 Challenges for Solving these Problems

As mentioned in the literature, there are mainly two major challenges
described in the following two subsections.

###  4.1 Exponential Number of Possible Worlds

As mentioned in Section 2 that if for a given uncertain graph with $m$ edges
will have $2^{m}$ number of possible worlds. Even for small values of $m$
(say, $m=100$), the number of possible worlds is excessively large ( more than
the number of atoms in this universe). Almost all the problems that have been
described in Section 3 requires to enumerate all the possible worlds to output
the answer accurately. However, due to bounded computational resources it is
not possible to consider all the possible worlds. Now, here the challenge is
that probabilistically how many samples to consider for the computation to
output the result such that the error is bounded by at most $\epsilon$.
Consider the $u-v$ Reliability Computation Problem as described in Section 3.
Let, $R(u,v)$ and $\hat{R}(u,v)$ be the $u\mbox{-}v$ reliability values when
all the sample graphs are considered and when all the graphs are not
considered, respectively. So the question here is that for a given $\epsilon$
and $\delta$ how many sample graphs to consider such that the following
inequity holds: $Pr[|R(u,v)-\hat{R}(u,v)|\leq\epsilon]\geq 1-\delta$. To
address this issue, several effective sampling techniques have been developed
such as recursive sampling Jin et al. (2011b), recursive stratified sampling
Li et al. (2014, 2015), lazy propagation sampling Li et al. (2015) and many
more. Also, Parchas et al. Parchas et al. (2014, 2015) proposed to generate
deterministic representative instances such that underlying graph properties
are preserved.

###  4.2 Gigantic Size of Real-World Networks

As described, large size of possible world can be handled by approximately
answering the result with high probability. However, if the size of network is
itself very large, then processing the graph becomes even frther difficult.
Recently, to address this issue a framework called _simultaneously processing
approach_ has been developed Zou et al. (2017). Basically, this method samples
a number of possible worlds independently at random, efficiently store them
with compact data structures (as many of the sampled possible worlds have
common substructure) and simultaneously process the query to generate the
results. However, literature in this category is very limited.

In the next section, we report the existing solution methodologies for the
problems reported in Section 3.

##  5 Exsisting Solution Methodologies

In this section, we briefly describe the existing solution methodologies of
the problems described in Section 3. First we start with the computational
problems on uncertain graphs.

###  5.1 Computational Problems

####  5.1.1 Reliability Computation

As mentioned previously, the reliability computation problem has been studied
in different variants such as two vertex reliability computation ($u-v$
reliability), For a given uncertain graph, trivial way to compute reliability
is to enumerate all the possible worlds and process each of them sequentially.
However, this approach leads to huge computational burden. Recently, Sasaki et
al. Sasaki et al. (2019) proposed an efficient technique to compute the
network reliability, which reduces the number of required possible worlds and
compute the bounds on the $k$-terminal reliability by efficiently constructing
_binary decision diagram_ , which is basically a directed acyclic graph.
Binary decision diagram has been previously used to compute the network
reliability on deterministic graphs as well Hardy et al. (2007). Reported
experimental results show that there proposed methodology leads to less
variance and less error rate. Jin et al. Jin et al. (2011b) studied the
distance constrained $u\mbox{-}v$ reliability problem and their main
contribution is to use the _Horvitz -Thomson Type Estimator_ and _Recursive
Sampling Estimator_ that efficiently combines a deterministic computational
procedure to boost up the estimation accuracy. Reported results show the
superior performance of these two estimators. Recently, Ke et al. Ke et al.
(2019) performed an in-depth bench marking study for the $s-t$ reliability
problem with different sampling strategies, i.e., Monte Carlo (MC) Sampling,
_B.F.S. with Indexing_ Zhu et al. (2015), _Recursive Sampling_ Jin et al.
(2011b), _Recursive Stratified Sampling_ Li et al. (2014, 2015), _Lazy
Propagation Sampling_ Li et al. (2015), _Indexing via Probabilistic Trees_
Maniu et al. (2017). Their goal was to make a comparative study of different
sampling strategies to understand their estimator variance, memory usage etc.

The most simplest sampling technique is the MC sampling. In this approach $k$
deterministic graphs $\mathcal{G}_{1}$, $\mathcal{G}_{2}$, $\ldots$,
$\mathcal{G}_{k}$ are sampled out from the possible world. Now, assume that
$I_{\mathcal{G}_{i}}(s,t)$ for all $i\in[k]$ denotes the boolean variable
whose value is $1$ if $s$ and $t$ is reachable from each other and $0$
otherwise. By this method, we have the following estimated reliability:

$R(s,t)\approx\hat{R}(s,t)=\frac{1}{k}\underset{i\in[k]}{\sum}I_{\mathcal{G}_{i}}(s,t)$
(14)

Here, the estimator $\hat{R}(s,t)$ is an unbiased estimator of the $s-t$
reliability, i.e., $\mathbb{E}[\hat{R}(s,t)]=R(s,t)$. Now, it has been shown
in Potamias et al. (2009) the number of Monte Carlo Samples required to reach
the $s-t$ reliability $\eta$ is greater than or equals to
$\frac{3}{\epsilon^{2}R(s,t)}ln(\frac{2}{\eta})$, i.e.,
$Pr[|\hat{R}(s,t)-R(s,t)|\geq\epsilon R(s,t)]\leq\eta$. Now, the traversing
each deterministic graph for checking required $\mathcal{O}(m+n)$ time. Hence,
the time requirement for reliability estimation using this technique is of
$\mathcal{O}(k(m+n))$.

Later Zhu et al. Zhu et al. (2015) proposed an offline sampling scheme which
is also space efficient. In this sampling scheme, the given uncertain graph
entirely stored without the existence probability of the edges. However, each
edge is associated with bit vector of length $k$. For any arbitrary edge $e\in
E(G)$, in its associated bit vector, the $i$-th entry is $1$ if the edge $e$
is present in $\mathcal{G}_{i}$. Now, it can be observed that the traversing
in this compact graph structure is equivalent to traversing each of the
sampled graph in parallel. It is easy to follow that the index building scheme
requires $\mathcal{O}(km)$ time and space requirement is of
$\mathcal{O}(n+km)$.

Jin et al. Jin et al. (2011b) proposed the ‘recursive sampling’ approach that
improves over the MC sampling due to the following two reasons. The first one
is that: for a given $s-t$ query, if some edges are already missing in a
possible world, then it may not be too much relevant whether other set of
edges are present or not. Secondly, many possible worlds share a significant
number of existing or missing edges. The working principal of this approach is
as follows. Starting with the vertex $s$, an extendable edge $e$ incident on
$s$ is randomly sampled for $k$ times. Now, the generated samples are divided
into two groups: one group containing $e$ and the other one is not containing
$e$. Assume, in the first group of samples by the edge $e$ the reachable node
is $w$ and now more edges are expandable. This process is repeated for both
the groups by picking up an randomly expandable edges and subdividing the
groups into smaller ones. A very similar approach was developed by Zhu et al.
Zhu et al. (2011) which is called as the _Dynamic MC Sampling_ technique.

Now, assume that $E_{1}\subseteq E(G)$ and $E_{2}\subseteq E(G)$ be the set of
present and non-present edges in one group. Let $G(E_{1},E_{2})$ denotes the
set of possible worlds, where the edges present in $E_{1}$ are present, though
the edges of $E_{2}$ are not present. The generation probability of the
deterministic graphs present in the group $G(E_{1},E_{2})$ is given by the
following equation:

$Pr_{G(E_{1},E_{2})\sqsubseteq G}=\underset{e\in
E_{1}}{\prod}P(e)\underset{e^{{}^{\prime}}\in
E_{2}}{\prod}(1-P(e^{{}^{\prime}}))$ (15)

Now, the $s-t$ reliability of the group $G(E_{1},E_{2})$ is basically the
probability that $s$ and $t$ are reachable when a deterministic graph
$\mathcal{G}$ from $G(E_{1},E_{2})$ are appearing and the following equation
computes this.

$R_{G(E_{1},E_{2})}(s,t)=\underset{\mathcal{G}\in
G(E_{1},E_{2})}{\sum}I_{\mathcal{G}}(s,t)\times\frac{Pr_{\mathcal{G}\sqsubseteq
G}}{Pr_{G(E_{1},E_{2})\sqsubseteq G}}$ (16)

Now, it is easy to verify that for any arbitrary edge $e\in
E(G)\setminus(E_{1}\cup E_{2})$ the following holds:

$R_{G(E_{1},E_{2})}(s,t)=P(e).R_{G(E_{1}\cup\\{e\\},E_{2})}(s,t)+(1-P(e))R_{G(E_{1},E_{2}\cup\\{e\\})}(s,t)$
(17)

This process continues till the $E_{1}$ contains an $s-t$ path with
$R_{G(E_{1},E_{2})}(s,t)=1$ or $E_{2}$ contains an $s-t$ cut with
$R_{G(E_{1},E_{2})}(s,t)=0$

Later, Li et al. Li et al. (2015) proposed the recursive stratified sampling
technique that works based on the divide-and-conquer paradigm. In this method,
the entire probability space is divided into $r+1$ non-overlapping subspaces
by selecting $r$ edges. Each division we call as ‘stratum’. Let $X$ be the set
of $r$ edges chosen via breadth first search from the source node $s$. Let,
$Y$ is a boolean matrix which stores the status value of the selected edges in
different stratum. $Y_{ij}$ will be equal to $1$ if the $j$-th ($1\leq j\leq
r$) edge belongs to the $i$-th stratumor not. Now, a deterministic graph
$\mathcal{G}$ from the possible world belongs to the $i$-th stratum is given
by the following equation:

$\pi_{i}=\underset{e_{j}\in X\wedge Y_{ij}=1}{\prod}P(e_{j})\underset{e_{j}\in
X\wedge Y_{ij}=0}{\prod}(1-P(e_{j}))$ (18)

The sample size of each stratum is fixed as $k_{i}=\pi_{i}.k$. Reliability is
computed in each of the stratum and the expected value is returned as the
$s-t$ reliability. It has been shown in Li et al. (2015) that the time
requirement for recursive stratified sampling is same as the MC sampling;
i.e.; $\mathcal{O}(k(m+n))$.

Li et al. Li et al. (2017) proposed the ‘lazy propagation sampling’ scheme.
The basic working principle of this method is as follows: “If the existence
probability of an edge is very low, then it quite natural that this edge will
not be present in many possible worlds, hence, it is not to probe such edges.
To describe formally, this method employs a _geometric distribution_
222https://en.wikipedia.org/wiki/Geometric_distribution in each edge and
probes an edge if it is activated. It has been shown in Li et al. (2017) that
the variance of the lazy propagation sampling is same as the MC sampling,
though it improves the efficiency.

Maniu et al. Maniu et al. (2017) proposed the ‘Indexing via Probabilistic
trees’ methodology for efficiently computing the $s-t$ reliability in
uncertain graphs. This method constructs a tree structure called as the
‘ProbTree’ from the given uncertain graph $G$. When a $s-t$ reliability query
$q$ comes, an equivalent graph $G(q)$ is created from the ‘ProbTree’ and the
MC sampling is done in $G(q)$ itself. If the size of $G(q)$ is smaller than
$G$, then the query $q$ can be evaluated very efficiently. They developed
three different indexing schemes, namely, _SPQR trees_ , _FWD_ , and _LIN
ProbTrees_. As per their analysis, among these three, the FWD (fixed width
tree decomposition) is the best because the both the _build time_ and _query
time_ of this data structure is linear and the query quality is ‘lossless’ for
$\omega\leq 2$, where $\omega$ is the width of the tree decomposition Alber
and Niedermeier (2002). As per the analysis in Maniu et al. (2017), the time
complexity of building the FWD ProbTree is linear in number of nodes of the
graph. However, the query execution time is of
$\mathcal{O}(k(n^{{}^{\prime}}+m^{{}^{\prime}}))$. Here, $n^{{}^{\prime}}$ and
$m^{{}^{\prime}}$ denotes the number of nodes and edges present in the graph
$G(q)$. The space complexity of this sampling scheme is of $\mathcal{O}(m)$.
Table 3 shows the time and space complexity of different sampling strategies
for the $s-t$ reliability problem. Table 4 summarizes the pros and cons of
different sampling techniques.

Table 3: Advantages and disadvantages of different sampling techniques for reliability computation Sampling Technique |  Time Complexity |  Space Complexity
---|---|---
_MC Sampling_ |  $\mathcal{O}(k(m+n))$ |  $\mathcal{O}(k(m+n))$
_B.F.S. with Indexing_ |  $\mathcal{O}(k(m+n))$ |  $\mathcal{O}(n+km)$
_Recursive Sampling_ |  $\mathcal{O}(nd)$ |  $\mathcal{O}(k(m+n))$
_Recursive Stratified Sampling_ |  $\mathcal{O}(k(m+n))$ |  $\mathcal{O}(rm)$
_Lazy Propagation Sampling_ |  $\mathcal{O}(k(m+n))$ |  $\mathcal{O}(n)$
_Indexing via Probabilistic Trees_ |  $\mathcal{O}(k(m+n))$ |  $\mathcal{O}(m)$
Table 4: Advantages and disadvantages of different sampling techniques for reliability computation Sampling Technique |  Advantages |  Disadvantages
---|---|---
_Monte Carlo Sampling_ |  • simple to understand • easy to implement • only one sample is required to store in the main memory |  • inefficient when the network is large • estimator variance is quite high
_B.F.S. with Indexing_ Zhu et al. (2015) |  • more efficient than MC Sampling • memory requirement is more than MC sampling (to store the bit vectors of the edges) |  • statistically same variance as the MC Sampling • same accuracy as the MC Sampling
_Recursive Sampling_ Jin et al. (2011b) |  • more efficient than MC Sampling |  • same variance as MC Sampling
_Recursive Stratified Sampling_ Li et al. (2014, 2015) |  • estimator variance is slightly reduced than MC Sampling. |  • same variance as MC Sampling • running time is also more than MC and B.F.S. with Indexing.
_Lazy Propagation Sampling_ Li et al. (2015) |  • efficiency improves over the MC sampling |  • same variance as the MC Sampling
_Indexing via Probabilistic Trees_ Maniu et al. (2017) |  • variance is less compared to MC Sampling |  • Index construction is complicated and takes more time.

####  5.1.2 Simrank Computation

To the best of our knowledge, Du et al. Du et al. (2015) first study the
problem of Simrank computation on uncertain graphs. They proposed a dynamic
programming approach to compute the probability values of the probabilistic
transition matrix, which works in linear time. To improve the efficiency
further, they came up with incremental dynamic programming (IDP) approach.
Reported results shows that the IDP approach converges much faster than the
naive dynamic programming.

Subsequently, Zhu et al. Zhu et al. (2016a) also studied the same problem.
They formalized the notion of random walk in uncertain graphs and also based
on this notion they show how one can define Simrank on uncertain graphs. It is
important to note that in case of uncertain graphs $k$ step transition
probability matrix (i.e., $W^{k}$) is not equal to $k$-th power of the one
step transition probability matrix ($W^{1}$). They defined the random walk on
uncertain graphs by exploiting the all possible worlds. For a given uncertain
graph $G(V,E,P)$, let $X_{0}$, $X_{1},\ldots,X_{n}$ be the random variable
associated with a random walk in $G$. Hence,
$Pr_{G}(X_{n}=v_{n}|X_{0}=v_{0},X_{1}=v_{1},\ldots,X_{n-1}=v_{n-1})$ can be
computed as follows:

$Pr_{G}(X_{n}=v_{n}|X_{0}=v_{0},X_{1}=v_{1},\ldots,X_{n-1}=v_{n-1})$
$=\underset{\mathcal{G}\in
L(G)}{\sum}Pr_{\mathcal{G}}(X_{n}=v_{n}|X_{0}=v_{0},X_{1}=v_{1},\ldots,X_{n-1}=v_{n-1}).Pr_{\mathcal{G}\sqsubseteq
G}$.

Now, applying the Markovian property,

$=\underset{\mathcal{G}\in
L(G)}{\sum}Pr_{\mathcal{G}}(X_{n}=v_{n}|X_{n-1}=v_{n-1}).Pr_{\mathcal{G}\sqsubseteq
G}$

$=Pr_{G}(X_{n}=v_{n}|X_{n-1}=v_{n-1})$.

Now, $k$-step transition probability from the vertex $u$ to $v$ can be
computed as follows:
$Pr_{G}(X_{n}=v|X_{n-k}=u)$
$=\underset{\mathcal{G}\in
L(G)}{\sum}Pr_{\mathcal{G}}(X_{n}=v|X_{n-k}=u).Pr_{\mathcal{G}\sqsubseteq
G}=\underset{\mathcal{G}\in
L(G)}{\sum}Pr_{\mathcal{G}}(u\rightarrow_{k}v).Pr_{\mathcal{G}\sqsubseteq G}$.

Let $W^{k}$ be the $k$-step transition matrix of the uncertain graph $G$.
$W^{k}$ can be computed by the following equation.

$W^{k}=\underset{\mathcal{G}\in L(G)}{\sum}Pr_{\mathcal{G}\sqsubseteq
G}\mathbb{W}_{\mathcal{G}}^{k}$ (19)

where $\mathbb{W}_{\mathcal{G}}^{k}$ denotes the $k$-step transition
probability matrix of the possible world $\mathcal{G}$. Based on this random
walk on uncertain graphs, they came up with four different approaches to
compute Simrank, namely, (i) baseline method, (ii) sampling technique, (iii)
two stage method, and (iv)speeding up techniques. Experimental results show
that the methods have very high scalability.

####  5.1.3 Clustering of Uncertain Graphs

To the best of our knowledge, Liu et al. Liu et al. (2012) first studied the
clustering problem on uncertain graphs. Suppose, given an uncertain graph
$G(V,E,P)$, we want to cluster the graph into $k$ clusters $C_{1}$, $C_{2}$,
$\ldots$, $C_{k}$. Consider any possible world $\mathcal{G}_{i}\in L(G)$ and
it has $L_{i}$ many connected components denoted as $CC^{i,1}$, $CC^{i,2}$,
$\ldots$, $CC^{i,L_{i}}$. The vertices of each connected component are also
divided into groups based on their cluster levels. As an example, the vertices
of the connected component $CC^{i,j}$ are denoted by $CC^{i,j}_{k}$. First,
they introduced the notion of _purity_ by the cluster level entropy as
follows:

$F_{p}=\underset{\mathcal{G}\in L(G)}{\sum}Pr_{\mathcal{G}\sqsubseteq
G}\underset{j=1}{\sum}^{L_{i}}|CC^{i,j}|.H(\underset{x\in[k]}{\bigcup}CC_{x}^{i,j})$
(20)

where
$H(\underset{x\in[k]}{\bigcup}CC_{k}^{i,j})=-\underset{x\in[k]}{\sum}\frac{|CC_{x}^{i,j}|}{|CC^{i,j}|}\log(\frac{|CC_{x}^{i,j}|}{|CC^{i,j}|})$
is the entropy of cluster levels for fragment $j$ for the $i$-th possible
world of $G$. As mentioned in Liu et al. (2012), if purity is the only
criteria then it may happen that the clustering process may leads to a single
cluster containing maximum number of nodes. To address this issue, Liu et al.
Liu et al. (2012) considered the notion of _size balance_ , which tells that
two clusters can not be too much imbalanced in terms of their sizes. Now, to
make the clusters size balanced the following function could be maximized.

$F_{e}=\underset{\mathcal{G}\in L(G)}{\sum}Pr_{\mathcal{G}\sqsubseteq
G}.n.H(\underset{x\in[k]}{\bigcup}C_{x})=n.H(\underset{x\in[k]}{\bigcup}C_{k})$
(21)

Here,
$H(\underset{k}{\bigcup}C_{k})=-\underset{x\in[k]}{\sum}\frac{|C_{x}|}{n}\log(\frac{|C_{x}|}{n})$.
Now, Liu et al. Liu et al. (2012) formulated the reliable clustering of an
uncertain graph as to minimize the following function:

$F=F_{p}-F_{e}$ (22)

They developed a novel $k$-means clustering algorithm to optimize the function
mentioned in Equation 22. Experimental results demonstrate the scalability of
this method.

Later, Ceccarello et al. Ceccarello et al. (2017b) also studied the uncertain
graph clustering problem from a different perspective. Here, the goal is to
partition the nodes of the uncertain graph into $k$ cluster in such a way that
each of the cluster features a node as a cluster center to maximize the
minimum or average reliability (minimum connection probability (MCP) and
average connection probability (ACP)) from the cluster center to the other
nodes of the cluster. They have shown that this problem is $\\#$P-Hard and
came up with approximation algorithms for both the MCP and ACP variants of
this problem. They have shown that their proposed methodologies generate a
$k$-clustering which gives $\Omega((P_{opt-min}(k))^{2})$ and
$\Omega((\frac{P_{opt-avg}(k)}{\log n})^{3})$ lower bound in approximation
guarantee, where $P_{opt-min}(k)$ and $P_{avg-min}(k)$ denotes the maximum and
average connection probability of any $k$-clustering. They compared their
results with deterministic weighted graph clustering algorithms to show the
efficiency of their proposed methodology.

Kollios et al. Kollios et al. (2011) extended the edit distance-based graph
clustering technique for uncertain graph. Given two deterministic graphs
$\mathcal{G}(V,E_{\mathcal{G}})$ and $Q(V,E_{Q})$, their graph edit distance
$ED(\mathcal{G},Q)$ is defined by the following equation.

$ED(\mathcal{G},Q)=|E_{\mathcal{G}}\setminus E_{Q}|+|E_{Q}\setminus
E_{\mathcal{G}}|$ (23)

Now, given an uncertain graph $G(V,E,P)$ and and a deterministic graph
$Q(V,E_{Q})$, their graph edit distance $ED(G,Q)$ can be given by the
following equation:

$ED(G,Q)=\underset{\mathcal{G}\in L(G)}{\sum}Pr_{\mathcal{G}\sqsubseteq
G}.ED(\mathcal{G},Q)$ (24)

Here, $ED(\mathcal{G},Q)$ can be computed using Equation 23. They introduced
the notion of _Cluster Graph_ , which is basically vertex disjoint
disconnected cliques, denoted as $C(V,E_{C})$. That means $V$ is partitioned
into $k$ disjoint sets $V_{1}$, $V_{2}$, $\ldots$, $V_{k}$, such that $\forall
i\in[k]$, $\forall v,v^{{}^{\prime}}\in V_{i},(vv^{{}^{\prime}})\in E_{C}$,
and $\forall i,j\in[k],i\neq j$, $v\in V_{i}$ and $v^{{}^{\prime}}\in V_{j}$,
$(vv^{{}^{\prime}})\notin E_{C}$. Now, given an uncertain graph $G(V,E,P)$,
its clustering problem basically asks to find out the cluster graph
$C(V,E_{C})$ such that the edit distance $ED(G,C)$ is minimized. They
exploited the connection between this problem with that of correlation
clustering and showed that the randomized expected $5$-approximation algorithm
proposed by Ailon et al. Ailon et al. (2008) for weighted correlation
clustering can be used for solving the uncertain graph clustering problem.
Experimental evaluations show that this algorithm generates statistically
significant clusters of an uncertain graph and also scale well on real-world
networks.

Halim et al. Halim et al. (2017) proposed a solution methodology for the
uncertain graph clustering problem by exploiting the neighborhood information.
By this method first the input uncertain graph is converted into a
deterministic graph by classification technique used for edge prediction, and
finally deterministic graph clustering technique can be used for clustering.
They also performed an experimental study with different classification
technique for edge prediction.

Subsequently, Han et al. Han et al. (2019) studied the uncertain graph
clustering problem with two different goals: divide the uncertain graph into
$k$-clusters such that (i) the average reliability from cluster center to
other nodes are maximized (similar to the $k$-median problem), and also (ii)
the minimum reliability between any node of the cluster to its cluster center
is maximized (similar to the $k$-center problem). Both $k$-center and
$k$-median problems has been studied extensively by the researchers of
theoretical computer scientists Thorup (2005); Mettu and Plaxton (2003). For
the $k$-median problem, they proposed an $(1-\frac{1}{e})$-factor
approximation algorithm, and also for the $k$-center problem they proposed an
$(1-\epsilon)OPT_{k}^{c}$ factor approximation (with high probability)
algorithm where $OPT_{k}^{c}$ is the optimal value for the $k$-center
objective function. Their experimental evaluation shows that proposed
approaches significantly out performs the methods proposed by Ceccarello et
al. Ceccarello et al. (2017b).

It is important to notice that though there are several clustering techniques
for uncertain graphs, however, the criteria is different across the
methodologies. Like, in Liu et al.’s Liu et al. (2012) study the goal is to
generate size balanced clusters, where as in Ceccarello et al.’s Ceccarello et
al. (2017b) study the goal is to cluster the uncertain graph to maximize the
average/minimum reliability within each cluster. Table 5 briefly summarizes
the uncertain graph clustering techniques.

Table 5: Summery of the Uncertain Graph Clustering Techniques. Reference |  Criteria for Clustering |  Main Contributions
---|---|---
Liu et al. Liu et al. (2012) |  To generate size balanced clustering of an uncertain graph. |  • Came up with a generalized reliability measurement based on purity and size balance. • Proposed a novel k-means algorithm for uncertain graph clustering.
Ceccarello et al. Ceccarello et al. (2017b) |  To cluster an uncertain graph such that the average/minimum reliability within each cluster is maximized. |  • Showed that the problem is $\mathcal{NP}$-Hard. • Proposed methodologies that gives approximation guarantee with respect to optimal $k$-Clustering.
Kollios et al. Kollios et al. (2011) |  To minimize the edit distance between cluster graph and input uncertain graph |  • Formulated the uncertain graph clustering problem as the general case of _Cluster Edit_ Problem. • Showed that the randomized algorithm for proposed by Ailon et al. (2008) can be used to solve the uncertain graph clustering problem
Halim et al. Halim et al. (2017) |  • No specific criteria mentioned. |  • Proposed a methodology that converts the uncertain graph to a deterministic one by applying edge classification technique so that existing deterministic graph clustering techniques can be used.
Han et al. Han et al. (2019) |  • No specific criteria mentioned. |  • Proposed a methodology that converts the uncertain graph to a deterministic one by applying edge classification technique so that existing deterministic graph clustering techniques can be used.

Next, we describe solution methodologies of various graph algorithmic problems
that has been studied in the context of uncertain graphs.

###  5.2 Querying Uncertain Graphs

####  5.2.1 Querying for Subgraph

Subgraph searching and querying in a graph database in deterministic setting
is a very well studied topic in data management community. However, in
probabilistic setting the amount of literature is very limited. Here, we
briefly summarize the existing literature.

##### Pattern Matching Queries

To the best of the author knowledge (also as per the authors’ claim) Zou et
al. Zou et al. (2009) were the first to study the subgraph pattern matching
queries on uncertain graphs. As the Subgraph Isomorphism Problem is NP-Hard
even in deterministic graphs, the same hardness result follows in the context
of uncertain graphs as well. Now, as the rechability problem is $\\#$P-Hard in
uncertain graphs, hence the subgraph pattern matching in uncertain graph is
also $\\#$P-Hard. So, the goal here was to find an approximate solution for
this problem. They proposed an efficient approach to check whether a subgraph
should be returned as a solution or not. They also derived a sample bound
which is $\frac{16.n.\log(\frac{2}{\delta})}{\epsilon^{2}.minsup}$ such that
the $Pr(|\hat{p}-Pr(F)|\geq\epsilon)\leq\delta$. Here, $\hat{p}$ is an
estimator of $Pr(F)$. This is the foundational work in this direction, and
subsequently many researchers gave deep dive in this direction.

Later Chen et al. Chen and Wang (2010) studied the approximate subgraph search
problem in uncertain graph stream. Here, given an uncertain graph stream
$<GS_{1},GS_{2},\ldots,GS_{k_{1}}>$, a set of query graphs
$<Q_{1},Q_{2},\ldots,Q_{k_{2}}>$, and a probability threshold $\epsilon$ the
goal here is to report all joinable pairs $<GS_{i,t}Q_{j}>$ in each time stamp
$t$. This means that the subgraph $Q_{j}$ is contained in $GS_{i}$ with
probability exceeding $\epsilon$, where $1\leq i\leq k_{1}$, $1\leq j\leq
k_{2}$, and $t\geq 0$. They proposed two efficient pruning technique, namely
‘structural pruning’ and ‘probability pruning’ which makes there methodology
efficient. Running time of their methodology is of $\mathcal{O}(\sqrt{n}m\log
m)$.

Later Yuan et al. Yuan et al. (2011b) studied the same problem and proposed
the ‘filtering and verifying’ strategy to speed up the search process. In the
filtering phase, a probabilistic inverted index is maintained which can be
used for probabilistic pruning. Next in the verification phase the remaining
candidates have been verified by exact algorithm. This method is tested with
both synthetic as well as real-world datasets. In a follow up work by yuan et
al. Yuan et al. (2014) Yuan et al. (2016), they developed probabilistic match
trees (PM Trees) based on match cuts and cut selection process. Considering
this index structure, they developed effective pruning strategy to prune the
unqualified matches. This makes the proposed methodology much more efficient,
and hence the sizes of the graphs that have been used in this study is much
larger than the previous works.

Chen et al. Chen et al. (2018) proposed the ‘enumeration-evaluation’ framework
for this problem, where first they enumerate all the candidate subgraphs and
then for each subgraph compute its support and decide whether to output this
as a result. They also showed that under the probabilistic semantic the
computation of ‘Support’ is #P-Complete. Hence, their solutions are
approximate in nature with accuracy guarantee. Experimental results show the
practical usability of the algorithms.

Recently, Ma et al. Ma et al. (2019) studied the problem of counting a given
motif present in an uncertain graph. Given a motif $M$, there goal was to
evaluate the occurrence statistics of $M$ such as probability mass function,
mean, and variance. Based on their sample size analysis, they showed that if
the number of samples are more than $\frac{ln\frac{2}{\delta}}{2\epsilon^{2}}$
then the absolute error is bounded by $\epsilon$ with probability
$(1-\delta)$. The running time of their methodology is
$\mathcal{O}(nmd^{|V_{M}|-2})$, where $|V_{M}|$ denotes the number of vertices
in the motif and $d$ denotes the maximum degree of the graph. In the
experimental study of this work the size of the datasets are much larger than
that has been used in previous studies.

##### Subgraph Similarity Search

Yuan et al. Yuan et al. (2012) Yuan et al. (2015) studied the subgraph
similarity search problem over uncertain graph databases. They showed that the
problem is $\\#$P-Complete. They used their previously developed ‘filter and
verify’ technique to gear up the search process. In the filtering phase they
develop lower and upper bound of subgraph similarity probability based on
probabilistic matrix index. For the verification phase they developed
efficient sampling approach to validate the remaining candidates. Experimental
results show that their methods are scalable.

Gu et al. Gu et al. (2016) studied the problem of similarity maximal all
matches in an uncertain graph database. Given an uncertain graph $G$, a query
graph $g$, distance threshold $d$, and probability threshold $\alpha$, a
deterministic graph $\mathcal{G}\in L(G)$ is a similarity maximal match of $q$
in $G$ under the vertex mapping $\mathcal{F}$, if there exist no other
deterministic graph $\mathcal{G}^{{}^{\prime}}\in L(G)$ such that under the
same vertex mapping $\mathcal{F}$, $Pr(Dist(\mathcal{G}^{{}^{\prime}},g)\leq
d)>Pr(Dist(\mathcal{G},g)\leq d)$. Here, $Dist(\mathcal{G}^{{}^{\prime}},g)$
is the edit distance between $\mathcal{G}^{{}^{\prime}}$ and $g$ Chen et al.
(2019). They proposed different speed up techniques such as partial graph
evaluation, vertex pruning, probability upper bound-based filtering, and the
incremental evaluation method. Experimental results show that they outperform
baseline methods in orders of magnitude.

Table 6 summarizes the literature for pattern matching and subgraph similarity
search queries on uncertain graphs.

Table 6: Summery of the literature of different structural pattern mining on uncertain graphs Type of Subgraph |  Author |  Major Findings
---|---|---
Any subgraph |  Zou et al. Zou et al. (2009) |  • first to study the subgraph pattern matching queries on uncertain graphs. • derived a sample bound which is $\frac{16.n.\log(\frac{2}{\delta})}{\epsilon^{2}.minsup}$ for subgraph similarity search
Chen et al. Chen and Wang (2010) |  • proposed two efficient pruning technique, namely ‘structural pruning’ and ‘probability pruning’ for solving the problem.
|  Yuan et al. Yuan et al. (2011b) Yuan et al. (2014) Yuan et al. (2016) |  • proposed ‘filtering and verifying’ strategy to speed up the search process • developed probabilistic match trees (PM Trees) based on match cuts and cut selection process • developed effective pruning strategy to prune the unqualified matches
|  Chen et al. Chen et al. (2018) |  • proposed the ‘enumeration-evaluation’ framework for this problem • showed that under the probabilistic semantic the computation of ‘Support’ is #P-Complete
|  Ma et al. Ma et al. (2019) |  • showed that if the number of samples are more than $\frac{ln\frac{2}{\delta}}{2\epsilon^{2}}$, the absolute error is bounded • proposed a methodology with running time $\mathcal{O}(nmd^{|V_{M}|-2})$
Subgraph Similarity |  Yuan et al. Yuan et al. (2012) Yuan et al. (2015) |  • showed that the subgraph similarity search problem is $\\#$P-Complete • developed lower and upper bound of subgraph similarity probability based on probabilistic matrix index
Gu et al. Gu et al. (2016) |  • proposed different speed up techniques such as partial graph evaluation, vertex pruning, probability upper bound-based filtering, and the incremental evaluation method.

##### Clique

Clique in a deterministic graph $\mathcal{G}$ is defined as the subset of the
vertices where every pair of them are adjacent to each other. A clique
$\mathcal{C}$ is said to be maximal if for any $v\in V(\mathcal{G})\setminus
C$, $\mathcal{C}\cup\\{v\\}$ is not a clique. A clique is said to be a
$k$-clique if the number of vertices in the clique is $k$. Zou et al. Zou et
al. (2010b) studied the Top-$k$ maximal clique finding problem in uncertain
graphs. They proposed a ‘branch and bound’ algorithm for this problem. Given
the uncertain graph $G$, first they construct the deterministic graph
$\hat{G}$ by removing the uncertainties from $G$. Now, they defined a clique
search tree where each node represents a distinct clique, the root be the
trivial clique $\phi$, and if $\mathcal{C}$ is a parent of a non root clique
$\mathcal{C}^{{}^{\prime}}$ then $\mathcal{C}\subset\mathcal{C}^{{}^{\prime}}$
with $|\mathcal{C}^{{}^{\prime}}|=|\mathcal{C}|+1$. Now, the problem reduces
to a tree searching problem and their algorithm is divided into the following
steps: pruning, computing maximal clique probability, expansion, and update.
Experimental results show that the methods are scalable.

Later, Mukherjee et al. Mukherjee et al. (2016) introduced the notion of an
$\alpha$-maximal clique in the context of uncertain graphs and studied
counting and enumeration problem of such cliques. They showed that this number
of an $n$ vertex uncertain graph is exactly $\binom{n}{\frac{n}{2}}$ and
proposed an enumeration algorithm of such cliques having running time of
$\mathcal{O}(n.2^{n})$. They also showed that the running time of their
proposed algorithm is $\mathcal{O}(\sqrt{n})$ of an optimal algorithm.
experimental evaluation showing the practical utility of the algorithm.
Experimental evaluation shows the practical utility of the algorithm.

Recently, Li et al. Li et al. (2019) studied the $(k,\tau)$-Clique search
problem in an uncertain graph. A clique $\mathcal{C}$ is said to be a
$(k,\tau)$-Clique if size of $\mathcal{C}$ is $k$ with clique probability at
least $\tau$, and also $\mathcal{C}$ is maximal. They proposed two core based
prunnning technique and one cut based prunning technique which makes the
search process more effective. Running time of their algorithm is of
$\mathcal{O}(2^{n^{{}^{\prime}}}(m^{{}^{\prime}}+n^{{}^{\prime}}))$. Here,
$m^{{}^{\prime}}$ and $n^{{}^{\prime}}$ denotes the number of edges and
vertices of the largest connected component in $(Top_{k},\tau)$-core which is
much smaller than the original uncertain graph. They defined the notion of
$(Top_{k},\tau)$-core as the Rashid et al. Rashid et al. (2019)

##### Truss

In a deterministic graph $\mathcal{G}$, its one subgraph $H$ is called a
$k$-truss if every edge of this subgraph is incident with at least $(k-2)$
tringles. Huang et al. Huang et al. (2016) studied the truss decomposition
problem in the context of uncertain graphs. They defined the notion of
$(k,\gamma)$-truss as a maximal connected subgraph $\mathcal{H}$, in which for
every edge, the probability that it is contained in at least $(k-2)$ triangles
is at least $\gamma$. They proposed a dynamic programming algorithm for
decomposing an uncertain graph into maximal such $(k,\gamma)$-truss. They also
defined the global $(k,\gamma)$-truss in which along with the previous
conditions, it has to satisfy that the probability that $\mathcal{H}$ contains
a $k$-truss is at least $\gamma$.

Subsequently, Zou and Zhu Zou and Zhu (2017) introduced the $\theta$-truss
decomposition problem ($\theta\in[0,1]$), where given an uncertain graph $G$,
the goal is to decompose it into the following set $\\{T_{i,\theta}:1\leq
i\leq k\\}$. Here, $k$ is the largest value for which $T_{k,\theta}$ is a
probabilistic truss. They showed that like deterministic graphs truss
decomposition in uncertain graphs also follow ‘uniqueness’ and ‘hierarchy’
property. They proposed an $\mathcal{O}(m^{1.5}.\mathcal{Q})$ time algorithm
to solve this problem. Here, $\mathcal{Q}$ is the maximum number of common
neighbor of the end vertices of any edge. In the worst case, it may be of
$\mathcal{O}(n)$. They also extend it to an external memory algorithm for this
problem for larger size uncertain graphs.

##### Core

In a deterministic graph $\mathcal{G}$, a subgraph $\mathcal{J}$ is said to be
a $k$-core of $\mathcal{G}^{{}^{\prime}}$ if $\forall v\in V(\mathcal{J})$,
$deg(u)$ in $\mathcal{J}$ is more than or equal to $k$ and also $\mathcal{J}$
is maximal. Bonchi et al. Bonchi et al. (2014) introduced the notion of
$(k,\eta)$-core, which is basically the maximal subgraph $\mathcal{J}$, such
that every vertex $v\in V(\mathcal{J})$ has degree more than or equal to $k$
with probability at least $\eta$. First, they showed that given an $\eta$, the
$(k,\eta)$-core decomposition of an uncertain graph is unique. They proposed a
dynamic programming algorithm for this problem having run time of
$\mathcal{O}(m\Delta)$, where $\Delta=\underset{v\in
V(G)}{max}(\underset{k}{max}(Pr[deg(v)\geq k]\geq\eta))$. They applied this
core decomposition approach to solve practical problems such as ‘influence
maximization’, ‘task driven team formation’.

Later, Peng et al. Peng et al. (2018) introduced the concept of
$(k,\theta)$-core of an uncertain graph which consists of set of nodes that is
a $k$-core with probability at least $\theta$. They showed that the problem of
computing $(k,\theta)$-core is NP-Hard. If
$\frac{1}{2\epsilon^{2}}.ln(\frac{2n}{\delta})$ many graphs are sampled from
the possible world then the estimation error of the $k$-core probability can
be bounded by $\epsilon$ with probability at least $(1-\delta)$. To further
reduce the computational burden in individual deterministic graphs, they
proposed a $k$-core membership check algorithm that makes their methodology
much faster.

##### Reliable Subgraph

Jin et al. Jin et al. (2011a) first defined the reliable subgraph search
problem in the context of uncertain graphs, which basically asks given an
$\alpha\in[0,1]$ determine all induced subgraphs of the input uncertain graph
such that the probability that the remains connected is greater than or equal
to $\alpha$. They showed if $\frac{2}{\epsilon^{2}}ln(\frac{2}{\delta})$ many
number of deterministic graphs can be sampled from the possible world then the
estimation error of the reliability of the induced subgraph by any subset of
vertices $V_{s}$ can be bounded by $\epsilon$ with probability at least
$(1-\delta)$. From this sampling scheme they defined a new problem called the
‘Frequent Cohesive Set problem’. A subset of the vertices of a graph is said
to be cohesive if the subgraph induced by the vertex subset is connected. They
developed a peeling algorithm which works from super sets to subsets during
the pattern discovery.

##### Nucleus

Nucleus decomposition of a graph is generalization of core and truss
decomposition Sariyuce et al. (2015). Recently, Esfahani et al. Esfahani et
al. (2020) studied the problem of nucleus decomposition of an uncertain
graphs. They have introduced the concept of ‘local’ ($l$), ‘global’($gl$), and
‘weakly global’ ($wg$) nucleus. Given an uncertain graph $G$, a triangle
$\Delta$, and $\mu\in\\{l,g,wg\\}$, the probability that the random variable
$X_{G,\Delta,\mu}$ takes the value $k$ with tail probability

$Pr[X_{G,\Delta,\mu}\geq k]=\underset{\mathcal{G}\in
L(G)}{\sum}Pr_{\mathcal{G}\sqsubseteq G}.I_{\mathcal{G},\Delta,\mu}$ (25)

Now, $I_{\mathcal{G},\Delta,l}=1$ if $\Delta$ is in $\mathcal{G}$ and the
support of $\Delta$ in $\mathcal{G}$ is at least $k$.
$I_{\mathcal{G},\Delta,gl}=1$ if $\Delta$ contained in $\mathcal{G}$, and
$\mathcal{G}$ is a deterministic $k$ nucleus. They showed that the local
version of the problem of nucleus decomposition is polynomial time solvable
whereas the global version is NP-Hard. They proposed a dynamic programming
approach for solving the local version. From the results they concluded that
compared to probabilistic core and truss decompositions, nucleus decomposition
significantly outperforms in terms of density and clustering metrics.

Table 7 summarizes the literature related to different structural patterns in
uncertain graph.

Table 7: Summery of the literature of different structural pattern mining on uncertain graphs Type of Subgraph |  Author |  Major Findings
---|---|---
Clique |  Zou et al. Zou et al. (2010b) |  • introduced the Top-$k$ maximal clique finding problem • proposed a branch and bound algorithm for this problem
Mukherjee et al. Mukherjee et al. (2016) |  • introduced the notion of $\alpha$-maximal clique • showed that the number of such cliques are $\binom{n}{\frac{n}{2}}$ • proposed an algorithm with running time $\mathcal{O}(n2^{n})$ • showed that their algorithm is $\mathcal{O}(\sqrt{n})$ of optimal algorithm
|  Li et al. Li et al. (2019) |  • introduced the notion of $(k,\tau)$-clique • proposed core and cut-based pruning technique • proposed an algorithm with running time of $\mathcal{O}(2^{n^{{}^{\prime}}}(m^{{}^{\prime}}+n^{{}^{\prime}}))$
Truss |  Huang et al. Huang et al. (2016) |  • introduced the truss decomposition problem in uncertain graphs • proposed a dynamic programming algorithm
Zou and Zhu Zou and Zhu (2017) |  • introduced the $\theta$-truss decomposition problem • showed that the truss decomposition follow ‘uniqueness’ and ‘hierarchy’ property • proposed an $\mathcal{O}(m^{1.5}.\mathcal{Q})$ time algorithm
Core |  Bonchi et al. Bonchi et al. (2014) |  • introduced the core decomposition problem in uncertain graphs • proposed an algorithm with running time $\mathcal{O}(m\Delta)$ • applied there approach to solve ‘influence maximization’ and ‘task driven team formation’
Peng et al. Peng et al. (2018) |  • introduced the concept of $(k,\theta)$-core of an uncertain graph • gave a sample bound to compute the $k$-core probability with bounded error • proposed a $k$-core membership check algorithm for speeding up the procedure
Reliable |  Jin et al. Jin et al. (2011a) |  • first defined the problem of reliable subgraph search on uncertain graphs • gave a sample bound to estimate the subgraph reliability with bounded error
Nucleus |  Jin et al. Jin et al. (2011a) |  • first defined the problem of reliable subgraph search on uncertain graphs • gave a sample bound to estimate the subgraph reliability with bounded error

###  5.3 Graph Algorithmic Problem

As mentioned in Section 3, among plethora of graph algorithmic problems, only
a very few has been studied on uncertain graphs. The first one is the
construction of ‘Minimum Spanning Tree (MST).’ Zhang et al. Zhang et al.
(2016) introduced and studied the problem of finding most reliable minimum
spanning tree. The trivial solution for this problem is to enumerate all the
possible worlds, compute the MST in each one of them and then choose one with
the highest probability value. However, it requires exponential time. To get
rid of this problem, Zhang et al. Zhang et al. (2016) proposed an incremental
greedy approach for this problem. Starting with an empty MST, until all the
vertices of the graph has been included in the MST this algorithm iteratively
choose an edge that connects the already build MST with maximum probability.
To implement this, they have used the ‘max heap’ data structure. Their
analysis shows that this algorithm is able to give a spanning tree having
reliability $(1-(\frac{1}{2})^{\frac{d}{2}})^{n-1}$ and expected approximation
ratio $(\frac{1}{2})^{dn}$, where $d$ is the maximum degree of the graph.
Computational time requirement of this algorithm is
$\mathcal{O}(d^{2}.n^{2})$. To the best of our knowledge, there is no other
study that on finding MST on uncertain graphs.

Another important problem which has been studied in the context of uncertain
graphs is the ‘link prediction problem’. Ahmed et al. Ahmed and Chen (2016)
studied this problem in uncertain social networks. They reduced the link
prediction problem in uncertain network to the problem of random walk in a
deterministic graph. They considered the ‘Simrank’ as the similarity metric
between two nodes. Their method consisting of the following two steps:

  * •

First step is the computation of the transformation matrix. For the given
probabilistic graph $G(V,E,P)$ and a deterministic graph
$\mathcal{G}(V,\mathcal{E})$, the associated transformation matrix can be
defined as follows:

$\overline{W}(u,u)=\underset{(uq)\in E(\mathcal{G})}{\prod}(1-P(uq))$ (26)
$\overline{W}(u,v)=\underset{G^{{}^{\prime}}\in\Omega(uv)}{\sum}\frac{A(u,v)}{\underset{(uq)\in
E(G^{{}^{\prime}})}{\sum}A(u,q)}Pr_{G^{{}^{\prime}}\sqsubseteq G}$ (27)

Where $A$ is the adjacency matrix of the uncertain graph $\mathcal{G}$, and
$\Omega(uv)$ is the subset of the possible worlds in which the edge $(u,v)$ is
present.

  * •

Second step is the computation of the Simrank matrix. Based on the computed
value of $\overline{W}$, this matrix is computed using the following equation:

$S=c.\overline{W}^{T}.S.\overline{W}+(1-c).I$ (28)

where, c is a constant having value in between $0$ and $1$, and $I$ is the
identity matrix.

Based on this computed Simrank value, for a given $k\in\mathbb{Z}^{+}$, vertex
pairs (which are not currently linked currently) corresponding top-$k$ values
are returned as the result.

Another algorithmic problem studied in the context of uncertain graph is the
‘information flow maximization’ problem. Frey et al. Frey et al. (2017, 2018)
showed that this problem is $NP$-Hard by a reduction from the _0-1 Knapsack
Problem_ Moradi et al. (2021). To highlight, they study this problem on vertex
weighted graphs, where vertex weight signifies the weight on the information
in the corresponding vertex. For a vertex $Q\in V(G)$, $flow(Q,G)$ denotes the
random variable signifying the total vertex weights of all the nodes $V(G)$
that are reachable from the node $Q$. As mentioned previously, rechability
problem in uncertain graphs is $\\#P$-Hard, hence the complexity of the
information flow estimation also falls in the same category. To tackle this
problem, they used traditional Monte Carlo Sampling to generate a subset of
possible worlds. It has been shown that the average value over these samples
is an unbiased estimator of the random variable $flow(Q,G)$. Next, they have
used the concept mono-connected nodes (two nodes are mono-connected if there
exist a single path connecting them and also for them the reliability can be
computed efficiently.), and bi-connected nodes (two nodes are mono-connected
if there exist two or more path connecting them). Next, they proposed the
_Flow Tree_ data structure which is an adoption of _Block Cut Tree_ Hopcroft
and Tarjan (1973); Westbrook and Tarjan (1992). As, finding the optimal
solution of this problem is $NP$-Hard, hence they proposed an incremental
greedy algorithm that generates sub-optimal solution for this problem.

###  5.4 Miscellaneous Problem

Among a few other problems, ‘graph sparcification’ has been studied in the
context of uncertain graphs. As mentioned previously, for a given
sparcification ratio $\alpha\in(0,1)$ and an uncertain graph $G(V,E,P)$ , this
problem is all about find a subgraph
$G^{{}^{\prime}}(V,E^{{}^{\prime}},P^{{}^{\prime}})$ such that
$E^{{}^{\prime}}\subset E$ and $|E^{{}^{\prime}}|=\alpha.|E|$. For this
problem Parchas et al. Parchas et al. (2018) proposed a cut-based
sparcification technique for uncertain graphs. First, they generalized the
notion of cut size for a given set of vertices $S$ in the context of uncertain
graph. Their proposed framework begins by initializing a connected unweighted
backbone graph $G_{b}$ and after that the two techniques are applied to
$G_{b}$ to generate the spercified graph. First, they proposed an approach to
initialize the backbone graph $G_{b}(V,E_{b})$. As described in Section 3.4.1,
the problem is to minimize the discrepancy, hence they formulated the
following optimization problem:

$\underset{p^{{}^{\prime}}}{min}|d-Y_{b}.p^{{}^{\prime}}|$

such that, $p^{{}^{\prime}}\in(0,1]^{|E_{b}|}$

where $d$ is a vector of size $|V(G)|$ containing the expected degree values
of the nodes of $G$ and $Y_{b}$ is the incidence matrix of size $|V(G)|\times
E_{b}$. Next, they showed that for the incidence matrix $A_{b}$ of $G_{b}$,
there exist a probability assignment $p^{*}$ that minimizes the discrepancy
for which the expected degree of any node is less than its original degree.
Using this result they showed that the optimal probability distribution
$p^{*}$ for the degree discrepancy $\delta_{A}$ is the solution of the
following linear programming problem (LPP):

$\underset{p^{{}^{\prime}}}{max}\ |p^{{}^{\prime}}|$

such that, $A_{b}.p^{{}^{\prime}}\leq d$

and $p^{{}^{\prime}}\in(0,1]^{|E_{b}|}$.

Now, this LPP can be solved using the solver packages like, _Simplex_ Ficken
(2015). They also proposed an efficient methodology ‘Gradient Decent Backbone’
which closely approximates the optimal probability assignment. The running
time of this methodology is of $\mathcal{O}(M_{steps}.\alpha.|E(G)|)$, where
$M_{steps}$ denotes the number of steps required to converge the gradient
decent method. This method only updates the edge probabilities without
inserting or removing edges. They proposed another methodology called
_Expectation Maximization Degree_ and this modifies both the backbone graph as
well as the edge probabilities. This procedure is inspired by the
_expectation-maximization_ , which is an iterative optimization framework and
also uses the Gradient Decent Backbone as a subroutine. Running time of this
methodology is that $\mathcal{O}(E_{steps}.\alpha.|E(G)|.(\log n+M_{steps}))$,
where $E_{steps}$ denotes the number of iterations required to converge this
process.

Another problem that has been studied in the context of uncertain graph is the
‘node classification’ problem. Dallachiesa et al. Dallachiesa et al. (2014)
proposed an iterative probabilistic learning approach to solve this. For any
unlabelled node $r$ in $G$ having neighbors $i_{1}$, $i_{2}$, $\ldots,i_{s}$
with labels $t_{1}$, $t_{2}$, $\ldots,t_{s}$, its probability is estimated by
the Bayes’ rule over the adjacent nodes’ neighbors. This is formalized by the
following equation:

$P(L(r)=p|L(i_{1})=t_{1},\ldots,L(i_{s})=t_{s})\propto
P(L(r)=p)\underset{x}{\prod}P(L(i_{x})=t_{x}|L(r)=p)$ (29)

However, if significant number of edges have low probability, then this method
will have an impact on the classification process. To get rid of this problem,
they proposed the iterative edge augmentation process. For this purpose, they
split the already labeled nodes ($T_{0}$) into two parts ‘training’
($T_{train}$) set and a ‘hold out’ set ($T_{hold}$). The ratio $T_{train}$ to
$T_{0}$ is basically a user defined parameter. Initially, starting with a
small fraction of high probability edges, this edge set is expanded with
incorporating the outside edges in an iterative manner. the ratio of active
edges are denoted by $\theta$. The value of $\theta$ for which maximum
accuracy is obtained is denoted by $\theta^{*}$. This can be obtained by
evaluating the accuracy on a number of sampled graphs.

Han et al. Han et al. (2015) studied the uncertain graph classification
problem using the _extreme learning machine_ , which was originally proposed
by Miche et al. Miche et al. (2009). Their method is broadly divided into
three steps. Firstly, we put forward a framework for classifying uncertain
graph objects. Secondly, we extend the traditional algorithm used in the
process of extracting frequent subgraphs to handle uncertain graph data.
Thirdly, based on Extreme Learning Machine (ELM) with fast learning speed, a
classifier is constructed.

##  6 Current Trends and Exsisting Research Gaps

After analyzing the reported literature, here we list out the current research
trends:

  * •

Bounds on Required Samples: As mentioned previously, for most of the problems
on uncertain graph how we can sample few of them to answer the problem within
bounded error with high probability. Recently, sample bounds are analyzed for
different problems studied on uncertain graphs. Sadeh et al. Sadeh et al.
(2019) studied this for the influence maximization problem. However, the same
study can be done for other problems as well.

  * •

Development of Efficient Indexing: Another way of reducing the computational
time of processing any uncertain graph is to index it properly using the
proposed indexing scheme. To the best of our knowledge, the only indexing
scheme is available for uncertain graphs is _probabilistic tree_ Maniu et al.
(2017). Much more indexing scheme can be developed which may lead to faster
execution of the query problems on uncertain graphs.

  * •

Finding Different structural Patterns: Recently several structural patterns
finding algorithms are developed for analyzing the topology. As an example,
Sun et al. Sun et al. (2021) proposed a methodology for indexing the trusses
of an uncertain graph. Such methods are not available in the literature for
other structural patterns.

  * •

Uncertain Graph Sparsification: A Plethora of literature is available for
sparsification of a deterministic graph Peleg and Schäffer (1989); Althöfer et
al. (1993); Fung et al. (2019). Recently, a cut-based spercification technique
has been developed for uncertain graphs. Certainly, there is a gap in this
area as the other principles of graph sparsification can be used for designing
the same for the uncertain graph.

  * •

Graph Algorithmic Problems: As mentioned previously, among plethora of graph
algorithmic problems, in last five years very few of them has been studied
such as spanning tree, link prediction, information flow maximization. There
is a research gap as the remaining algorithmic graph theory problems can be
studied under the uncertain graph framework.

Next, we proceed to describe the future research directions in this domain.

##  7 Future Research Directions

Based on the detailed analysis of the existing literature, in this section, we
describe a number of future research directions.

  * •

Definition of Uncertainty: In the existing literature, the notion of
uncertainty is defined as the probabilistic existence of the edges of the
graph. However, it can be observed that this not the only notion of
uncertainty. The same thing applies to the vertices as well. Hence all the
problems mentioned in Section 3, that has been under edge uncertainty model,
can also be studied under node uncertainty model as well. Very recently,
Fukunaga et al. Fukunaga (2019) studied a well studied graph theoretic problem
Connected Dominating Set Problem under the node uncertainty setting.

  * •

Modeling the Problem: Before applying any principles and approaches of
uncertain graph mining, it is important to represent the input network as an
uncertain graph, and for that it is very much vital to decide which uncertain
model is going to fit.

  * •

Studying Existing Graph Theoretic Problems in Uncertain Graph Framework: There
are tons of graph theoretic problems which has been studied by theoretical
computer scientist. However, as mentioned in Section 3, very few of them have
been studied in uncertain graph framework. So, naturally it appears that there
are many problems which has not been studied yet in uncertain graph framework.
it will be interesting to take an existing problem and study in uncertain
graph framework. Also, different model of uncertainty may give altogether
different flavor to the problem.

  * •

Efficient Sampling Scheme: There are many problems in uncertain graph mining
domain, such as rechability (i.e., reliability computation), subgraph
enumeration and many more, where sampling of the deterministic graphs from the
possible worlds play a crucial role. It will be very important contribution to
come up with efficient sampling technique, that can beat the existing
techniques in atleast any one of the following two metrics: either (i) it
should take less number of samples compared to the existing methods, or (ii)
it should be able to answer to the queries with higher probability.

  * •

Information Flow Maximization Problem: In Frey et. al.’s Frey et al. (2017)
study of this problem, they have only consider the Monte-Carlo Sampling.
However, as mentioned previously, there are many other and more efficient
sampling techniques are there. Those sampling techniques can be used solve the
problem even more efficiently.

  * •

Incorporation of Temporal Nature: In almost entire existing literature, it has
been considered that the assigned probability values to the edges are fixed
over the time. However, in reality the case is not the same. As mentioned
previously, the influence graph of a social network often represented as an
uncertain graph. The links of a social network are time varying, and also if
the probability values marked on the edges are considered as the diffusion
probability that can also change with time Laurent et al. (2015).

  * •

Querying of Combinatotial Structures: As mentioned in Section 3.1, finding and
counting motifs in networks is important problem. There are different kinds of
motifs that are available in network science literature, such as _Clan_ ,
_Core_ , _Club_ and their different generalizations. However, it is surprising
to observe that there are very few structures which have been studied in
uncertain graph framework. So, it will be an interesting future work to
develop efficient algorithms for finding remaining structural patterns in an
uncertain graphs.

  * •

Solution Methodologies for Modern Hardware: Recent times have witnessed a
significant development in almost every aspects computer architecture,
starting from processor and accelerator design to memory system or subsystem
organization Deng et al. (2017); Kloda et al. (2019). Also, several new
computing paradigms have been introduced, such as _map reduce_ and many more.
For deterministic graph mining there exist some literature, which developed
algorithms for modern computing paradigms Xiang et al. (2013); Chen et al.
(2016a). Similarly, for uncertain graph mining also algorithms can be
developed in the context of modern computing paradigms.

  * •

Scalability of the Methodologies: Day by day the size of the real-world
networks are increasing. As an example, it can be observed that for the social
influence maximization problem (a problem in the domain of social network
analysis, where the underlying social network is represented as an uncertain
graph) the experimentation of the very first paper by Kempe et al. Kempe et
al. (2003) uses dataset of size $10748$ nodes and $53000$ edges. However, a
very recent paper on the same problem by Zeng et al. Zeng et al. (2020) uses
dataset of size $41.7\times 10^{6}$ nodes and $1.5\times 10^{9}$ edges. So, to
deal with this kind of gigantic networks, it is essential that the solution
methodologies should have high scalability. Hence, developing highly scalable
methods for large scale uncertain graphs will remain major thrust in this
area.

  * •

Privacy Preserving Uncertain Graph Mining: As mentioned previously, the
privacy preserving aspects has been deeply inducted with data mining in recent
times. However, in the context of uncertain graphs this study is extremely
limited Tian et al. (2018); Xiao et al. (2018). So, more research work can be
carried out in this direction.

  * •

System Oriented Research: Since last one decade or so, a significant effort
has been made to develop graph processing systems Zhu et al. (2016b); Malewicz
et al. (2010). Please look into McCune et al. (2015); Shi et al. (2018); Besta
et al. (2019). However, none of the studies consider the uncertain nature of
the graph. So, it will be an interesting future work to develop uncertain
graph processing and mining system, which includes efficient data structures
for storing, efficient processing algorithm developed based on processor
architecture, and also very effective data visualization, and interpretation
component to represent the output.

##  8 Concluding Remarks

In this paper, we have presented a concise and almost self contained survey on
the uncertain graph mining and analysis with a major focus on three aspects,
namely, different problems studied in this domain, challenges for solving
those problems, and existing solution methodologies. After analyzing the
existing literature, we have derived the current research trend. At the end,
we have listed a number of future research directions. Hope that this survey
will help the upcoming researchers and practitioners to have finer
understanding and better exposure in this field.

## References

  * Adar and Re (2007) Adar E, Re C (2007) Managing uncertainty in social networks. IEEE Data Eng Bull 30(2):15–22
  * Aggarwal (2010) Aggarwal CC (2010) Managing and mining uncertain data, vol 35. Springer Science & Business Media
  * Aggarwal and Wang (2010) Aggarwal CC, Wang H (2010) A survey of clustering algorithms for graph data. In: Managing and mining graph data, Springer, pp 275–301
  * Ahmed and Chen (2016) Ahmed NM, Chen L (2016) An efficient algorithm for link prediction in temporal uncertain social networks. Information Sciences 331:120–136
  * Ahuja et al. (1988) Ahuja RK, Magnanti TL, Orlin JB (1988) Network flows
  * Ailon et al. (2008) Ailon N, Charikar M, Newman A (2008) Aggregating inconsistent information: ranking and clustering. Journal of the ACM (JACM) 55(5):23
  * Alber and Niedermeier (2002) Alber J, Niedermeier R (2002) Improved tree decomposition based algorithms for domination-like problems. In: Latin American Symposium on Theoretical Informatics, Springer, pp 613–627
  * Althöfer et al. (1993) Althöfer I, Das G, Dobkin D, Joseph D, Soares J (1993) On sparse spanners of weighted graphs. Discrete & Computational Geometry 9(1):81–100
  * Ball (1986) Ball MO (1986) Computational complexity of network reliability analysis: An overview. IEEE Transactions on Reliability 35(3):230–239
  * Ball et al. (1995) Ball MO, Colbourn CJ, Provan JS (1995) Network reliability. Handbooks in operations research and management science 7:673–762
  * Bell and Iida (1997) Bell MG, Iida Y (1997) Transportation network analysis
  * Besta et al. (2019) Besta M, Stanojevic D, Licht JDF, Ben-Nun T, Hoefler T (2019) Graph processing on fpgas: Taxonomy, survey, challenges. arXiv preprint arXiv:190306697
  * Bhagat et al. (2011) Bhagat S, Cormode G, Muthukrishnan S (2011) Node classification in social networks. In: Social network data analytics, Springer, pp 115–148
  * Bollobás and Béla (2001) Bollobás B, Béla B (2001) Random graphs. 73, Cambridge university press
  * Bonchi et al. (2014) Bonchi F, Gullo F, Kaltenbrunner A, Volkovich Y (2014) Core decomposition of uncertain graphs. In: Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp 1316–1325
  * Brecht and Colbourn (1988) Brecht TB, Colbourn CJ (1988) Lower bounds on two-terminal network reliability. Discrete applied mathematics 21(3):185–198
  * Brohee and Van Helden (2006) Brohee S, Van Helden J (2006) Evaluation of clustering algorithms for protein-protein interaction networks. BMC bioinformatics 7(1):488
  * Carrington et al. (2005) Carrington PJ, Scott J, Wasserman S (2005) Models and methods in social network analysis, vol 28. Cambridge university press
  * Ceccarello et al. (2017a) Ceccarello M, Fantozzi C, Pietracaprina A, Pucci G, Vandin F (2017a) Clustering uncertain graphs. Proceedings of the VLDB Endowment 11(4):472–484
  * Ceccarello et al. (2017b) Ceccarello M, Fantozzi C, Pietracaprina A, Pucci G, Vandin F (2017b) Clustering uncertain graphs. PVLDB 11(4):472–484, DOI 10.1145/3186728.3164143, URL http://www.vldb.org/pvldb/vol11/p472-ceccarello.pdf
  * Chen and Wang (2010) Chen L, Wang C (2010) Continuous subgraph pattern search over certain and uncertain graph streams. IEEE Transactions on Knowledge and Data Engineering 22(8):1093–1109
  * Chen et al. (2016a) Chen Q, Fang C, Wang Z, Suo B, Li Z, Ives ZG (2016a) Parallelizing maximal clique enumeration over graph data. In: International Conference on Database Systems for Advanced Applications, Springer, pp 249–264
  * Chen et al. (2013) Chen W, Lakshmanan LV, Castillo C (2013) Information and influence propagation in social networks. Synthesis Lectures on Data Management 5(4):1–177
  * Chen et al. (2016b) Chen W, Lin T, Yang C (2016b) Real-time topic-aware influence maximization using preprocessing. Computational social networks 3(1):8
  * Chen et al. (2019) Chen X, Huo H, Huan J, Vitter JS (2019) An efficient algorithm for graph edit distance computation. Knowledge-Based Systems 163:762–775
  * Chen et al. (2018) Chen Y, Zhao X, Lin X, Wang Y, Guo D (2018) Efficient mining of frequent patterns on uncertain graphs. IEEE Transactions on Knowledge and Data Engineering 31(2):287–300
  * Coon et al. (2018) Coon JP, Badiu MA, Gündüz D (2018) On the conditional entropy of wireless networks. In: 2018 16th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt), IEEE, pp 1–6
  * Cormen et al. (2009) Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to algorithms. MIT press
  * Dallachiesa et al. (2014) Dallachiesa M, Aggarwal C, Palpanas T (2014) Node classification in uncertain graphs. In: Proceedings of the 26th International Conference on Scientific and Statistical Database Management, ACM, p 32
  * Deng et al. (2017) Deng Y, Ni Y, Li Z, Mu S, Zhang W (2017) Toward real-time ray tracing: A survey on hardware acceleration and microarchitecture techniques. ACM Computing Surveys (CSUR) 50(4):1–41
  * Diestel (2012) Diestel R (2012) Graph theory, volume 173 of. Graduate texts in mathematics p 7
  * Du et al. (2015) Du L, Li C, Chen H, Tan L, Zhang Y (2015) Probabilistic simrank computation over uncertain graphs. Information Sciences 295:521–535
  * Erlebach et al. (2008) Erlebach T, Hoffmann M, Krizanc D, Mihal’Ák M, Raman R (2008) Computing minimum spanning trees with uncertainty. arXiv preprint arXiv:08022855
  * Esfahani et al. (2020) Esfahani F, Srinivasan V, Thomo A, Wu K (2020) Nucleus decomposition in probabilistic graphs: Hardness and algorithms. arXiv preprint arXiv:200601958
  * Ficken (2015) Ficken FA (2015) The simplex method of linear programming. Courier Dover Publications
  * Frey et al. (2017) Frey C, Züfle A, Emrich T, Renz M (2017) Efficient information flow maximization in probabilistic graphs. IEEE Transactions on Knowledge and Data Engineering 30(5):880–894
  * Frey et al. (2018) Frey C, Züfle A, Emrich T, Renz M (2018) Efficient information flow maximization in probabilistic graphs (extended abstract). In: 34th IEEE International Conference on Data Engineering, ICDE 2018, Paris, France, April 16-19, 2018, pp 1801–1802, DOI 10.1109/ICDE.2018.00258, URL https://doi.org/10.1109/ICDE.2018.00258
  * Fukunaga (2019) Fukunaga T (2019) Adaptive algorithm for finding connected dominating sets in uncertain graphs. arXiv preprint arXiv:191212665
  * Fung et al. (2019) Fung WS, Hariharan R, Harvey NJ, Panigrahi D (2019) A general framework for graph sparsification. SIAM Journal on Computing 48(4):1196–1223
  * Göbel and Jagers (1974) Göbel F, Jagers A (1974) Random walks on graphs. Stochastic processes and their applications 2(4):311–336
  * Gu et al. (2016) Gu Y, Gao C, Wang L, Yu G (2016) Subgraph similarity maximal all-matching over a large uncertain graph. World Wide Web 19(5):755–782
  * Guo and Jerrum (2019) Guo H, Jerrum M (2019) A polynomial-time approximation algorithm for all-terminal network reliability. SIAM Journal on Computing 48(3):964–978
  * Halim et al. (2017) Halim Z, Waqas M, Baig AR, Rashid A (2017) Efficient clustering of large uncertain graphs using neighborhood information. International Journal of Approximate Reasoning 90:274–291
  * Han et al. (2015) Han D, Hu Y, Ai S, Wang G (2015) Uncertain graph classification based on extreme learning machine. Cognitive Computation 7(3):346–358
  * Han et al. (2019) Han K, Gui F, Xiao X, Tang J, He Y, Cao Z, Huang H (2019) Efficient and effective algorithms for clustering uncertain graphs. Proceedings of the VLDB Endowment 12(6):667–680
  * Hardy et al. (2007) Hardy G, Lucet C, Limnios N (2007) K-terminal network reliability measures with binary decision diagrams. IEEE Transactions on Reliability 56(3):506–515
  * Hopcroft and Tarjan (1973) Hopcroft J, Tarjan R (1973) Algorithm 447: efficient algorithms for graph manipulation. Communications of the ACM 16(6):372–378
  * Huang et al. (2016) Huang X, Lu W, Lakshmanan LV (2016) Truss decomposition of probabilistic graphs: Semantics and algorithms. In: Proceedings of the 2016 International Conference on Management of Data, pp 77–90
  * Jain et al. (1999) Jain AK, Murty MN, Flynn PJ (1999) Data clustering: a review. ACM computing surveys (CSUR) 31(3):264–323
  * Jeh and Widom (2002) Jeh G, Widom J (2002) Simrank: a measure of structural-context similarity. In: Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, ACM, pp 538–543
  * Jin et al. (2011a) Jin R, Liu L, Aggarwal CC (2011a) Discovering highly reliable subgraphs in uncertain graphs. In: Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, pp 992–1000
  * Jin et al. (2011b) Jin R, Liu L, Ding B, Wang H (2011b) Distance-constraint reachability computation in uncertain graphs. Proceedings of the VLDB Endowment 4(9):551–562
  * Kassiano et al. (2016) Kassiano V, Gounaris A, Papadopoulos AN, Tsichlas K (2016) Mining uncertain graphs: An overview. In: Algorithmic Aspects of Cloud Computing - Second International Workshop, ALGOCLOUD 2016, Aarhus, Denmark, August 22, 2016, Revised Selected Papers, pp 87–116, DOI 10.1007/978-3-319-57045-7“˙6, URL https://doi.org/10.1007/978-3-319-57045-7_6
  * Ke et al. (2018) Ke X, Teo M, Khan A, Yalavarthi VK (2018) A demonstration of perc: probabilistic entity resolution with crowd errors. Proceedings of the VLDB Endowment 11(12):1922–1925
  * Ke et al. (2019) Ke X, Khan A, Quan LLH (2019) An in-depth comparison of st reliability algorithms over uncertain graphs. Proceedings of the VLDB Endowment 12(8):864–876
  * Kempe et al. (2003) Kempe D, Kleinberg J, Tardos É (2003) Maximizing the spread of influence through a social network. In: Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, ACM, pp 137–146
  * Khan et al. (2014) Khan A, Bonchi F, Gionis A, Gullo F (2014) Fast reliability search in uncertain graphs. In: EDBT, pp 535–546
  * Khan et al. (2018a) Khan A, Bonchi F, Gullo F, Nufer A (2018a) Conditional reliability in uncertain graphs. IEEE Transactions on Knowledge and Data Engineering 30(11):2078–2092
  * Khan et al. (2018b) Khan A, Ye Y, Chen L (2018b) On uncertain graphs. Synthesis Lectures on Data Management 10(1):1–94
  * Kloda et al. (2019) Kloda T, Solieri M, Mancuso R, Capodieci N, Valente P, Bertogna M (2019) Deterministic memory hierarchy and virtualization for modern multi-core embedded systems. In: 2019 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), IEEE, pp 1–14
  * Kollios et al. (2011) Kollios G, Potamias M, Terzi E (2011) Clustering large probabilistic graphs. IEEE Transactions on Knowledge and Data Engineering 25(2):325–336
  * Kong et al. (2013) Kong X, Yu PS, Wang X, Ragin AB (2013) Discriminative feature selection for uncertain graph classification. In: Proceedings of the 2013 SIAM International Conference on Data Mining, SIAM, pp 82–93
  * Kuramochi and Karypis (2005) Kuramochi M, Karypis G (2005) Finding frequent patterns in a large sparse graph. Data mining and knowledge discovery 11(3):243–271
  * Laurent et al. (2015) Laurent G, Saramäki J, Karsai M (2015) From calls to communities: a model for time-varying social networks. The European Physical Journal B 88(11):301
  * Lee et al. (2012) Lee J, Han WS, Kasperovics R, Lee JH (2012) An in-depth comparison of subgraph isomorphism algorithms in graph databases. In: Proceedings of the VLDB Endowment, VLDB Endowment, vol 6, pp 133–144
  * Lewis (1983) Lewis HR (1983) Computers and intractability. a guide to the theory of np-completeness
  * Li et al. (2010a) Li C, Han J, He G, Jin X, Sun Y, Yu Y, Wu T (2010a) Fast computation of simrank for static and dynamic information networks. In: Proceedings of the 13th International Conference on Extending Database Technology, ACM, pp 465–476
  * Li et al. (2012) Li J, Zou Z, Gao H (2012) Mining frequent subgraphs over uncertain graph databases under probabilistic semantics. The VLDB Journal 21(6):753–777
  * Li et al. (2010b) Li L, Wang H, Gao H, Li J (2010b) Eif: a framework of effective entity identification. In: International conference on web-age information management, Springer, pp 717–728
  * Li et al. (2014) Li RH, Yu JX, Mao R, Jin T (2014) Efficient and accurate query evaluation on uncertain graphs via recursive stratified sampling. In: 2014 IEEE 30th International Conference on Data Engineering, IEEE, pp 892–903
  * Li et al. (2015) Li RH, Yu JX, Mao R, Jin T (2015) Recursive stratified sampling: A new framework for query evaluation on uncertain graphs. IEEE Transactions on Knowledge and Data Engineering 28(2):468–482
  * Li et al. (2019) Li RH, Dai Q, Wang G, Ming Z, Qin L, Yu JX (2019) Improved algorithms for maximal clique search in uncertain networks. In: 2019 IEEE 35th International Conference on Data Engineering (ICDE), IEEE, pp 1178–1189
  * Li and Chen (2009) Li X, Chen H (2009) Recommendation as link prediction: a graph kernel-based machine learning approach. In: Proceedings of the 9th ACM/IEEE-CS joint conference on Digital libraries, ACM, pp 213–216
  * Li et al. (2017) Li Y, Fan J, Zhang D, Tan KL (2017) Discovering your selling points: Personalized social influential tags exploration. In: Proceedings of the 2017 ACM International Conference on Management of Data, pp 619–634
  * Liben-Nowell and Kleinberg (2007) Liben-Nowell D, Kleinberg J (2007) The link-prediction problem for social networks. Journal of the American society for information science and technology 58(7):1019–1031
  * Liu et al. (2012) Liu L, Jin R, Aggarwal C, Shen Y (2012) Reliable clustering on uncertain graphs. In: 2012 IEEE 12th International Conference on Data Mining, IEEE, pp 459–468
  * Ma et al. (2019) Ma C, Cheng R, Lakshmanan LV, Grubenmann T, Fang Y, Li X (2019) Linc: a motif counting algorithm for uncertain graphs. Proceedings of the VLDB Endowment 13(2):155–168
  * Ma et al. (2020) Ma C, Cheng R, Lakshmanan LV, Grubenmann T, Fang Y, Li X (2020) Linc: A motif counting algorithm for uncertain graphs. Proceedings of the VLDB Endowment 13(2)
  * Malewicz et al. (2010) Malewicz G, Austern MH, Bik AJ, Dehnert JC, Horn I, Leiser N, Czajkowski G (2010) Pregel: a system for large-scale graph processing. In: Proceedings of the 2010 ACM SIGMOD International Conference on Management of data, pp 135–146
  * Malkov et al. (2014) Malkov Y, Ponomarenko A, Logvinov A, Krylov V (2014) Approximate nearest neighbor algorithm based on navigable small world graphs. Information Systems 45:61–68
  * Maniu et al. (2017) Maniu S, Cheng R, Senellart P (2017) An indexing framework for queries on probabilistic graphs. ACM Transactions on Database Systems (TODS) 42(2):13
  * Martínez et al. (2017) Martínez V, Berzal F, Cubero JC (2017) A survey of link prediction in complex networks. ACM Computing Surveys (CSUR) 49(4):69
  * McCune et al. (2015) McCune RR, Weninger T, Madey G (2015) Thinking like a vertex: a survey of vertex-centric frameworks for large-scale distributed graph processing. ACM Computing Surveys (CSUR) 48(2):1–39
  * Megow et al. (2017) Megow N, Meißner J, Skutella M (2017) Randomization helps computing a minimum spanning tree under uncertainty. SIAM Journal on Computing 46(4):1217–1240
  * Mettu and Plaxton (2003) Mettu RR, Plaxton CG (2003) The online median problem. SIAM Journal on Computing 32(3):816–832
  * Miche et al. (2009) Miche Y, Sorjamaa A, Bas P, Simula O, Jutten C, Lendasse A (2009) Op-elm: optimally pruned extreme learning machine. IEEE transactions on neural networks 21(1):158–162
  * Moradi et al. (2021) Moradi N, Kayvanfar V, Rafiee M (2021) An efficient population-based simulated annealing algorithm for 0–1 knapsack problem. Engineering with Computers pp 1–20
  * Mukherjee et al. (2015) Mukherjee AP, Xu P, Tirthapura S (2015) Mining maximal cliques from an uncertain graph. In: 2015 IEEE 31st International Conference on Data Engineering, IEEE, pp 243–254
  * Mukherjee et al. (2016) Mukherjee AP, Xu P, Tirthapura S (2016) Enumeration of maximal cliques from an uncertain graph. IEEE Transactions on Knowledge and Data Engineering 29(3):543–555
  * Mukherjee et al. (2017) Mukherjee AP, Xu P, Tirthapura S (2017) Enumeration of maximal cliques from an uncertain graph. IEEE Trans Knowl Data Eng 29(3):543–555, DOI 10.1109/TKDE.2016.2527643, URL https://doi.org/10.1109/TKDE.2016.2527643
  * Parchas et al. (2014) Parchas P, Gullo F, Papadias D, Bonchi F (2014) The pursuit of a good possible world: extracting representative instances of uncertain graphs. In: Proceedings of the 2014 ACM SIGMOD international conference on management of data, ACM, pp 967–978
  * Parchas et al. (2015) Parchas P, Gullo F, Papadias D, Bonchi F (2015) Uncertain graph processing through representative instances. ACM Transactions on Database Systems (TODS) 40(3):20
  * Parchas et al. (2018) Parchas P, Papailiou N, Papadias D, Bonchi F (2018) Uncertain graph sparsification. IEEE Transactions on Knowledge and Data Engineering 30(12):2435–2449
  * Peleg and Schäffer (1989) Peleg D, Schäffer AA (1989) Graph spanners. Journal of graph theory 13(1):99–116
  * Peng et al. (2018) Peng Y, Zhang Y, Zhang W, Lin X, Qin L (2018) Efficient probabilistic k-core computation on uncertain graphs. In: 2018 IEEE 34th International Conference on Data Engineering (ICDE), IEEE, pp 1192–1203
  * Potamias et al. (2009) Potamias M, Bonchi F, Gionis A, Kollios G (2009) Nearest-neighbor queries in probabilistic graphs. Tech. rep., Boston University Computer Science Department
  * Potamias et al. (2010) Potamias M, Bonchi F, Gionis A, Kollios G (2010) K-nearest neighbors in uncertain graphs. Proceedings of the VLDB Endowment 3(1-2):997–1008
  * Rashid et al. (2019) Rashid A, Kamran M, Halim Z (2019) A top down approach to enumerate $\alpha$-maximal cliques in uncertain graphs. Journal of Intelligent & Fuzzy Systems 36(4):3129–3141
  * Roussopoulos et al. (1995) Roussopoulos N, Kelley S, Vincent F (1995) Nearest neighbor queries. In: ACM sigmod record, ACM, vol 24, pp 71–79
  * Sadeh et al. (2019) Sadeh G, Cohen E, Kaplan H (2019) Sample complexity bounds for influence maximization. arXiv preprint arXiv:190713301
  * Sariyuce et al. (2015) Sariyuce AE, Seshadhri C, Pinar A, Catalyurek UV (2015) Finding the hierarchy of dense subgraphs using nucleus decompositions. In: Proceedings of the 24th International Conference on World Wide Web, pp 927–937
  * Sasaki et al. (2019) Sasaki Y, Fujiwara Y, Onizuka M (2019) Efficient network reliability computation in uncertain graphs. In: EDBT, pp 337–348
  * Schulz et al. (2016) Schulz C, Nocaj A, Goertler J, Deussen O, Brandes U, Weiskopf D (2016) Probabilistic graph layout for uncertain network visualization. IEEE transactions on visualization and computer graphics 23(1):531–540
  * Sharara et al. (2011) Sharara H, Sopan A, Namata G, Getoor L, Singh L (2011) G-pare: a visual analytic tool for comparative analysis of uncertain graphs. In: 2011 IEEE Conference on Visual Analytics Science and Technology (VAST), IEEE, pp 61–70
  * Shi et al. (2018) Shi X, Zheng Z, Zhou Y, Jin H, He L, Liu B, Hua QS (2018) Graph processing on gpus: A survey. ACM Computing Surveys (CSUR) 50(6):1–35
  * Spielman and Srivastava (2011) Spielman DA, Srivastava N (2011) Graph sparsification by effective resistances. SIAM Journal on Computing 40(6):1913–1926
  * Sun et al. (2021) Sun Z, Huang X, Xu J, Bonchi F (2021) Efficient probabilistic truss indexing on uncertain graphs. In: Proceedings of the Web Conference 2021, pp 354–366
  * Taranto et al. (2012) Taranto C, Di Mauro N, Esposito F (2012) Uncertain (multi) graphs for personalization services in digital libraries. In: Italian Research Conference on Digital Libraries, Springer, pp 141–152
  * Thorup (2005) Thorup M (2005) Quick k-median, k-center, and facility location for sparse graphs. SIAM Journal on Computing 34(2):405–432
  * Tian et al. (2018) Tian Y, Yan J, Hu J, Wu Z (2018) A privacy preserving model in uncertain graph mining. In: 2018 International Conference on Networking and Network Applications (NaNA), IEEE, pp 102–106
  * Westbrook and Tarjan (1992) Westbrook J, Tarjan RE (1992) Maintaining bridge-connected and biconnected components on-line. Algorithmica 7(1-6):433–464
  * Whalen et al. (2015) Whalen K, Sadkhin B, Davidson D, Gerlt J (2015) Sequence similarity networks for the protein universe. The FASEB Journal 29(1_supplement):573–17
  * Xiang et al. (2013) Xiang J, Guo C, Aboulnaga A (2013) Scalable maximum clique computation using mapreduce. In: 2013 IEEE 29th International Conference on Data Engineering (ICDE), IEEE, pp 74–85
  * Xiao et al. (2018) Xiao D, Eltabakh MY, Kong X (2018) Sharing uncertain graphs using syntactic private graph models. In: 2018 IEEE 34th International Conference on Data Engineering (ICDE), IEEE, pp 1336–1339
  * Yalavarthi et al. (2017a) Yalavarthi VK, Ke X, Khan A (2017a) Probabilistic entity resolution with imperfect crowd. CoRR
  * Yalavarthi et al. (2017b) Yalavarthi VK, Ke X, Khan A (2017b) Select your questions wisely: For entity resolution with crowd errors. In: Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, ACM, pp 317–326
  * Yan et al. (2005) Yan X, Yu PS, Han J (2005) Substructure similarity search in graph databases. In: Proceedings of the 2005 ACM SIGMOD international conference on Management of data, ACM, pp 766–777
  * Yin et al. (2007) Yin X, Han J, Philip SY (2007) Object distinction: Distinguishing objects with identical names. In: 2007 IEEE 23rd International Conference on Data Engineering, IEEE, pp 1242–1246
  * Yuan et al. (2011a) Yuan Y, Wang G, Wang H, Chen L (2011a) Efficient subgraph search over large uncertain graphs. Proc VLDB Endowment 4(11):876–886
  * Yuan et al. (2011b) Yuan Y, Wang G, Wang H, Chen L (2011b) Efficient subgraph search over large uncertain graphs. Proc VLDB Endowment 4(11):876–886
  * Yuan et al. (2012) Yuan Y, Wang G, Chen L, Wang H (2012) Efficient subgraph similarity search on large probabilistic graph databases. arXiv preprint arXiv:12056692
  * Yuan et al. (2014) Yuan Y, Wang G, Chen L (2014) Pattern match query in a large uncertain graph. In: Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management, pp 519–528
  * Yuan et al. (2015) Yuan Y, Wang G, Chen L, Wang H (2015) Graph similarity search on large uncertain graph databases. The VLDB Journal 24(2):271–296
  * Yuan et al. (2016) Yuan Y, Wang G, Chen L, Ning B (2016) Efficient pattern matching on big uncertain graphs. Information Sciences 339:369–394
  * Zeng et al. (2020) Zeng X, Zhang S, Tang B (2020) Rcelf: A residual-based approach for influence maximization problem. arXiv preprint arXiv:200106630
  * Zhang et al. (2016) Zhang A, Zou Z, Li J, Gao H (2016) Minimum spanning tree on uncertain graphs. In: International Conference on Web Information Systems Engineering, Springer, pp 259–274
  * Zhang and Zaïane (2019) Zhang C, Zaïane OR (2019) Neighbor-based link prediction with edge uncertainty. In: Advances in Knowledge Discovery and Data Mining - 23rd Pacific-Asia Conference, PAKDD 2019, Macau, China, April 14-17, 2019, Proceedings, Part II, pp 462–474, DOI 10.1007/978-3-030-16145-3“˙36, URL https://doi.org/10.1007/978-3-030-16145-3_36
  * Zhao et al. (2014) Zhao B, Wang J, Li M, Wu FX, Pan Y (2014) Detecting protein complexes based on uncertain graph model. IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) 11(3):486–497
  * Zhu et al. (2011) Zhu K, Zhang W, Zhu G, Zhang Y, Lin X (2011) Bmc: an efficient method to evaluate probabilistic reachability queries. In: International Conference on Database Systems for Advanced Applications, Springer, pp 434–449
  * Zhu et al. (2015) Zhu R, Zou Z, Li J (2015) Top-k reliability search on uncertain graphs. In: 2015 IEEE International Conference on Data Mining, IEEE, pp 659–668
  * Zhu et al. (2016a) Zhu R, Zou Z, Li J (2016a) Simrank computation on uncertain graphs. In: 2016 IEEE 32nd International Conference on Data Engineering (ICDE), IEEE, pp 565–576
  * Zhu et al. (2017) Zhu R, Zou Z, Li J (2017) Simrank on uncertain graphs. IEEE Transactions on Knowledge and Data Engineering 29(11):2522–2536
  * Zhu et al. (2016b) Zhu X, Chen W, Zheng W, Ma X (2016b) Gemini: A computation-centric distributed graph processing system. In: 12th $\\{$USENIX$\\}$ Symposium on Operating Systems Design and Implementation ($\\{$OSDI$\\}$ 16), pp 301–316
  * Zou (2013) Zou Z (2013) Polynomial-time algorithm for finding densest subgraphs in uncertain graphs. In: Proceedings of MLG Workshop
  * Zou and Zhu (2017) Zou Z, Zhu R (2017) Truss decomposition of uncertain graphs. Knowledge and Information Systems 50(1):197–230
  * Zou et al. (2009) Zou Z, Li J, Gao H, Zhang S (2009) Frequent subgraph pattern mining on uncertain graph data. In: Proceedings of the 18th ACM conference on Information and knowledge management, ACM, pp 583–592
  * Zou et al. (2010a) Zou Z, Gao H, Li J (2010a) Discovering frequent subgraphs over uncertain graph databases under probabilistic semantics. In: Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, ACM, pp 633–642
  * Zou et al. (2010b) Zou Z, Li J, Gao H, Zhang S (2010b) Finding top-k maximal cliques in an uncertain graph. In: 2010 IEEE 26th International Conference on Data Engineering (ICDE 2010), IEEE, pp 649–652
  * Zou et al. (2017) Zou Z, Li F, Li J, Li Y (2017) Scalable processing of massive uncertain graph data: A simultaneous processing approach. In: 2017 IEEE 33rd International Conference on Data Engineering (ICDE), IEEE, pp 183–186