% ensure same length columns on last page (might need two sub-sequent latex runs)
\begin{table*}[htbp]
\centering
\begin{tabular}{l c c c c c c c }
\hline
\small Graph &   $\theta$    &  $\left | V_{N} \right | / \left |  V_T \right |/\left | V_C \right |$    &   $\left |E_{N}  \right |/\left | E_T \right |  /\left | E_C \right | $    &   $k_{Nmax}/k_{Tmax}/k_{Cmax}$    &   $ \text{PD}_{N}/\text{PD}_T/\text{PD}_C$ &   $\text{PCC}_{N}/\text{PCC}_T/\text{PCC}_C$ & $  \text{Time}_N/\text{Time}_T/\text{Time}_C$ \\
\midrule
%dblp  &    0.1   &    $19/34/115$   &    $171/561/6555$  &   $9/14/26$    & $0.785/0.611/0.264$   & $0.800/0.620/0.317$  \\
\small dblp  &    0.1   &    $19/34/115$   &    $171/561/6555$  &   $9/14/26$    & $0.800/0.611/0.264$   & $0.790/0.620/0.317$ & $   25/100/15.86$  \\
%dblp  &    0.3   &    $14/26/138$   &    $108/366/6693$  & $7/11/23$  & $0.888/0.698/0.277$ & $0.880/0.704/0.384$  \\
\small dblp  &    0.3   &    $14/26/138$   &    $108/366/6693$  & $7/11/23$  & $0.9917/0.785/0.277$ & $0.9918/0.789/0.384$ & $  11/30/16.99$  \\
\midrule
\small pokec &    0.1   &  $13/72/288$     &   $121/1335/10592$    &   $3/8/27$    &    $0.678/0.341/0.129$   & $ 0.636/0.393/0.170$ & $  672/1162/4401$\\
\small pokec &    0.3   &  $6/71/278$     &   $21/1031/10142$    &   $2/6/25$    &    $0.815/0.321/0.132$   & $0.793/0.406/0.172$ & $ 298/980/4349$\\
\midrule
\small biomine &  0.1  &   $103/102/430$    &  $5231/5127/92200$     &   $18/33 /79$    &   $0.540/0.538 /0.211 $    & $0.540/0.538/0.217$ & $ 1098/7642/5792$ \\
\small biomine &  0.3   &    $7/102 /431 $   &   $23/5125/92625$    &   $2/28/73$    &    $0.714/0.538/0.212 $   & $0.701/0.539/ 0.218$ & $ 939/1563/5685$\\
\hline
% ljournal-2208 &       &       &       &       &       & \\
% \bottomrule
\end{tabular}%
% \vspace{-0.2cm}
\caption{\textbf{Cohesiveness statistics of $\pmb{l}$-$\pmb{(k,\theta)}$-nucleus N, $\pmb{(k,\theta)}$-truss, T, and $\pmb{(k,\theta)}$-core, C on \textit{dblp}, \textit{pokec}, and \textit{biomine}. The number of vertices ($\pmb{\left | V_{N} \right | / \left |  V_T \right |/\left | V_C \right |}$), the number of edges ($\pmb{\left |E_{N}  \right |/\left | E_T \right |  /\left | E_C \right | }$), maximum nucleus/truss/core score ($\pmb{k_{Nmax}/k_{Tmax}/k_{Cmax}}$), the probabilistic density (PD$\pmb{_{N}/}$PD$\pmb{_{T}/}$PD$\pmb{_{C}/}$), and the probabilistic clustering coefficient (PCC$\pmb{_{N}/}$PCC$\pmb{_{T}/}$PCC$\pmb{_{C}/}$), respectively. %\textcolor{blue}{
The last column shows the time required for computing nucleus, truss, and core decomposition.}%}
\label{densitycompare}%
\vspace{-0.7cm}
\end{table*}%
\begin{figure}
\centering
\subfloat{ %font=\fontsize{4.5}{5}\selectfont
\begin{tikzpicture}
%[width=6.3cm, xlabel near ticks, ylabel near ticks, name = plot4, title={$\eta = 0.3$}, every axis title/.style={below right,at={(0.3,0.98)}}, legend style={draw=yellow, at={(0.98,0.98)},anchor=north east,nodes={scale=0.5}},xmode=normal,ymode=log,legend entries={dblp, flickr, biomine, cnr-2000, arabic-2005, uk-2005, ljournal-2008, twitter-2010},
%reverse legend, xlabel=Iteration,%ytick align=outside
%  ticklabel style = {font=\tiny},nodes near coords align=horizontal]
\begin{axis}[
%bar width = 0.2cm,
bar width = 0.1cm,
%xtick pos=left,
%ytick pos=left,
%title={Average Density},
%every axis title/.style={below right,at={(0.3,0.98)}},
legend style={font=\fontsize{7.5}{6}\selectfont,%font=\small,
draw = none, %at={(0.85,0.999)},anchor=north east,nodes={scale=0.8}}, legend cell align={left},
at={(0.01,0.999)},anchor=north west,nodes={scale=0.8}}, legend cell align={left},
%\addlegendentry{Probabilistic truss decomposition by \\ $h$-index based updating,Probabilistic truss decomposition by edge peeling},
%legend entries={Probabilistic truss decomposition by $h$-index based updating,Probabilistic truss decomposition by edge peeling},
legend entries={},
%enlarge y limits  = 0.4,
ymin = 0.7,
ytick align=inside,
ytick distance =0.05,
xtick style={draw=none},
%legend style={at={(0.5,-0.2)},
%anchor=north,legend columns=-1},
%reverse legend,el pos = near coords,
%ymax = 100000,
%ticklabel style = {font=\tiny},
ylabel={\textbf{Average PD/PCC}},
ylabel near ticks,
ylabel style={font=\fontsize{6}{6}\selectfont},
symbolic x coords={1,5,10,%
xlabel style = {font=\fontsize{6.5}{6}\selectfont},
%x tick label style={/pgf/number format/1000 sep=},
%ticklabel style = {font=\tiny},
ticklabel style = {font=\fontsize{7.5}{6}\selectfont},
legend style={font=\fontsize{7.5}{6}\selectfont,%font=\small,
draw = none, %at={(0.85,0.999)},anchor=north east,nodes={scale=0.8}}, legend cell align={left},
at={(0.999,0.999)},anchor=north east,nodes={scale=0.7}}, legend cell align={left},
%\addlegendentry{Probabilistic truss decomposition by \\ $h$-index based updating,Probabilistic truss decomposition by edge peeling},
%legend entries={Probabilistic truss decomposition by $h$-index based updating,Probabilistic truss decomposition by edge peeling},
legend entries={\textbf{PD},\textbf{PCC}},
%nodes near coords,
%every node near coord/.append style={align=left, rotate=60, anchor=west,font=\fontsize{6}{6}\selectfont},
%point meta=rawy,
%nodes near coords align={horizontal},
%nodes near coords style={rotate=90},
%x tick label style={rotate=45,anchor=east},
\addplot[fill = red] coordinates { %PD
(1,0.80) (5,0.86) (10,0.92) (15,0.93)
%(cnr-2000,420.29) (ljournal-2008,28210.269)
%(biomine,17e2) %(cnr-2000,420)
\addplot[fill = storeClusterComponent] coordinates { %PCC
(1,0.75) (5,0.85) (10,0.89) (15,0.9)
%(cnr-2000,420.29) (ljournal-2008,28210.269)
%(biomine,17e2) %(cnr-2000,420)
%\addlegendentry{Probabilistic truss}

%\legend{Probabilistic truss decomposition by $h$-index\_based updating, Probabilistic truss decomposition by edge peeling }
\end{axis}
\end{tikzpicture}
\hspace{0.1cm}
\subfloat{ %font=\fontsize{4.5}{5}\selectfont
\begin{tikzpicture}
%[width=6.3cm, xlabel near ticks, ylabel near ticks, name = plot4, title={$\eta = 0.3$}, every axis title/.style={below right,at={(0.3,0.98)}}, legend style={draw=yellow, at={(0.98,0.98)},anchor=north east,nodes={scale=0.5}},xmode=normal,ymode=log,legend entries={dblp, flickr, biomine, cnr-2000, arabic-2005, uk-2005, ljournal-2008, twitter-2010},
%reverse legend, xlabel=Iteration,%ytick align=outside
%  ticklabel style = {font=\tiny},nodes near coords align=horizontal]
\begin{axis}[
%bar width = 0.2cm,
bar width = 0.1cm,
%xtick pos=left,
%ytick pos=left,
%title={Average Density},
%every axis title/.style={below right,at={(0.3,0.98)}},
legend style={font=\fontsize{7.5}{6}\selectfont,%font=\small,
draw = none, %at={(0.85,0.999)},anchor=north east,nodes={scale=0.8}}, legend cell align={left},
at={(0.01,0.999)},anchor=north west,nodes={scale=0.7}}, legend cell align={left},
%\addlegendentry{Probabilistic truss decomposition by \\ $h$-index based updating,Probabilistic truss decomposition by edge peeling},
%legend entries={Probabilistic truss decomposition by $h$-index based updating,Probabilistic truss decomposition by edge peeling},
legend entries={},
enlarge y limits  = 0.004,
ymode = log,
ymin = 1,
ytick align=inside,
%ytick distance =10,
xtick style={draw=none},
%legend style={at={(0.5,-0.2)},
%anchor=north,legend columns=-1},
%reverse legend,el pos = near coords,
%ymax = 100000,
%ticklabel style = {font=\tiny},
ylabel={\textbf{Average \#of Nuclei/Edges}},
ylabel near ticks,
ylabel style={font=\fontsize{6}{6}\selectfont},
symbolic x coords={1,5,10,%
xlabel style = {font=\fontsize{6.5}{6}\selectfont},
%x tick label style={/pgf/number format/1000 sep=},
%ticklabel style = {font=\tiny},
ticklabel style = {font=\fontsize{7.5}{6}\selectfont},
legend style={font=\fontsize{7.5}{6}\selectfont,%font=\small,
draw = none, %at={(0.85,0.999)},anchor=north east,nodes={scale=0.8}}, legend cell align={left},
at={(0.999,0.999)},anchor=north east,nodes={scale=0.8}}, legend cell align={left},
%\addlegendentry{Probabilistic truss decomposition by \\ $h$-index based updating,Probabilistic truss decomposition by edge peeling},
%legend entries={Probabilistic truss decomposition by $h$-index based updating,Probabilistic truss decomposition by edge peeling},
legend entries={\textbf{\# of Edges},\textbf{\# of Nuclei}},
%nodes near coords,
%every node near coord/.append style={align=left, rotate=60, anchor=west,font=\fontsize{6}{6}\selectfont},
%point meta=rawy,
%nodes near coords align={horizontal},
%nodes near coords style={rotate=90},
%x tick label style={rotate=45,anchor=east},
\addplot[fill = dbscan] coordinates {  %edges
(1,504) (5,407) (10,229) (15,51)
%(1,51) (5,229) (10,407) (15,504)
\addplot[fill = blue] coordinates { %nuclei
(1,210) (5,25) (10,9) (15,6)
%\addlegendentry{Probabilistic truss}

%\legend{Probabilistic truss decomposition by $h$-index\_based updating, Probabilistic truss decomposition by edge peeling }
\end{axis}
\end{tikzpicture}

\vspace{-0.3cm}
\caption{\textbf{Average PD and PPC, average number of edges, average number of $\l$-$\pmb{(k,\theta)}$-nuclei for \textit{flickr} with $\pmb{\theta=0.3}$.} }
\label{avedensflickr}
\end{figure}

\balance
\subsection{Quality Evaluation of Nucleus subgraph}\label{density}
In this section, we compare the cohesiveness of $\l$-$(k,\theta)$-nucleus with the cohesiveness of local $(k,\gamma)$-truss~\cite{huang2016truss} and $(k,\eta)$-core~\cite{bonchi2014core}. We use two metrics. The first metric is the probabilistic density (PD) of a graph $\G$, which we denote by $\text{PD}(\G)$ and is defined as follows~\cite{huang2016truss}:
\begin{equation}
\text{PD}(\G) = \frac{\sum_{e \in E} p(e)}{\frac{1}{2} \left | V \right | \cdot (\left | V \right |-1)},
\end{equation}
In words, the PD of a probabilistic graph is the ratio of the sum of the existence probability of edges to the possible number of edges that a graph can have.

The second metric is probabilistic clustering coefficient (PCC). It measures the level of tendency of the nodes to cluster together.
Given a probabilistic graph $\G$, its PCC is defined as follows~\cite{huang2016truss,pfeiffer2011methods}:
\begin{equation}
\text{PCC}(\G) =  \frac{3 \sum_{\t_{uvw} \in \G}p(u,v) \cdot p(v,w) \cdot p(u,w)}{\sum_{(u,v),(u,w), v \neq w }p(u,v) \cdot p(u,w)}.
\end{equation}

For the probabilistic nucleus, probabilistic truss and probabilistic core subgraphs, we use the same threshold $\theta=\gamma=\eta$, set to 0.1 and 0.3. ($\gamma$ is used as threshold in the truss case \cite{huang2016truss}, and $\eta$ is used as threshold in the core case~\cite{bonchi2014core})
Also, we consider connectivity condition when outputting these subgraphs.
Table~\ref{densitycompare} reports the results on \textit{dblp}, \textit{pokec}, and \textit{biomine}. We removed the results for other datasets, since the behavior is similar to what we see for the datasets in the table.
For a given threshold, we report the statistics of local $(k_{Nmax},\theta)$-nucleus, $(k_{Tmax},\gamma)$-truss, and $(k_{Cmax},\eta)$-core,
where $k_{Nmax}$, $k_{Tmax}$, and $k_{Cmax}$ are maximum nucleus, truss and core scores, respectively. Also, for $k_{Nmax}$, $k_{Tmax}$, and $k_{Cmax}$, we might obtain more than one connected component; we report the average statistics over such components.
We denote
by $V_N,V_T,V_C$, the sets of nodes,
by $E_N,E_T,E_C$, the sets of edges,
by $PD_N,PD_T,PD_C$, the PD's
and by $PCC_N,PCC_T,PCC_C$, the PCC's
of nucleus, truss, and core components, respectively. %\textcolor{blue}{
The last column shows the running time for computing each decomposition. We observe that sometimes nucleus decomposition is faster than truss decomposition. This is because in nucleus decomposition there could be fewer triangles that survive the specified threshold in terms of support than edges in truss decomposition.

As can be seen in the table, $(k_{Nmax},\theta)$-nucleus produces high quality results in terms of PD and PCC.
%In fact, since $(k_{Nmax}$,$\theta)$-nucleus is a stronger definition of cohesive subgraph, it removes the triangles with small probability, and as a result edges with small probability cannot be part of a nucleus subgraph. In addition, triangles should have enough probability to be a part of many $4$-cliques. Therefore,
We achieve a significantly higher PD and PCC for nucleus compared to truss and core.
For instance, for {\em dblp} the PD for nucleus is 0.8 versus 0.611 and 0.264 for truss and core, which translates for nucleus being about 30\% and 200\% more dense than truss and core.
Similar conclusions can be drawn for PCC as well. %\textcolor{blue}{Moreover, as the running times show, in the nucleus decomposition algorithm, many triangles can be processed very fast since their degrees cannot be greater than the threshold.}

%Another interesting point is that since the numbers of edges and vertices in the nucleus subgraph is significantly smaller than those of truss and core, the probability that such subgraph exists in reality is high. Also, even for small values of $\theta=0.1$, $(k_{Nmax},\theta)$-nucleus is still a dense subgraph. Therefore, depending on the application threshold can be set to small values to obtained more number of vertices and edges for each component while maintaining density.

Moreover, Figure~\ref{avedensflickr} reports the average PD, the average PCC, the average edges in each $\l$-$(k,\theta)$-nucleus, and the number of connected components ($\l$-$(k,\theta)$-nuclei) for an example dataset \textit{flickr} with fixed $\theta=0.3$ and varying $k$. The first two sub-figures show that even for small values of $k$, PD and PCC are considerably high (above 70-80\%). In general, PD and PCC become larger as $k$ increases, since denser $\l$-$(k,\theta)$-nuclei will be detected by removing triangles having low support probability to be part of a $4$-clique.
This causes the final subgraphs to have edges with high existence probability only. Furthermore, since $\l$-$(k,\theta)$-nucleus implies connectivity, the number of connected components increases as $k$ decreases. It results in an increase in the average number of edges in each $\l$-$(k,\theta)$-nuclei (see the last two sub-figures).

Finally, we also compare the PD and PCC values of
$\g$-$(k,\theta)$-nucleus, $\w$-$(k,\theta)$-nucleus %\textcolor{blue}{
over 5 runs of these algorithms
, and
$\l$-$(k,\theta)$-nucleus, for
\textit{krogan}, \textit{flickr}, and \textit{dblp} datasets using $\theta = 0.001$, and %\textcolor{blue}{
averaging over all the possible values of $k$.
%The maximum value of $k$ is equal to $3$.
The results are shown in Figure~\ref{densityglob}.
We see that $\g$-$(k,\theta)$-nucleus achieves higher cohesiveness as expected.
In addition, $\w$-$(k,\theta)$-nucleus exhibits quite good PD and PCC values higher than those for $\l$-$(k,\theta)$-nucleus.

%On \textit{krogan} dataset, $\w$-$(k,\theta)$-nucleus and $\l$-$(k,\theta)$-nucleus are similar in terms of PD and PCC with $\l$-$(k,\theta)$-nucleus having slightly higher values. However, for the remaining datasets, the $\l$-$(k,\theta)$-nucleus has the least cohesiveness values.
\begin{figure}
\centering
\subfloat{
\begin{tikzpicture}
%[width=6.3cm, xlabel near ticks, ylabel near ticks, name = plot4, title={$\eta = 0.3$}, every axis title/.style={below right,at={(0.3,0.98)}}, legend style={draw=yellow, at={(0.98,0.98)},anchor=north east,nodes={scale=0.5}},xmode=normal,ymode=log,legend entries={dblp, flickr, biomine, cnr-2000, arabic-2005, uk-2005, ljournal-2008, twitter-2010},
%reverse legend, xlabel=Iteration,%ytick align=outside
%  ticklabel style = {font=\tiny},nodes near coords align=horizontal]
\begin{axis}[
%bar width = 0.2cm,
bar width = 0.1cm,
legend style={font=\fontsize{6}{6}\selectfont,%font=\small,
draw = none, %at={(0.85,0.999)},anchor=north east,nodes={scale=0.8}}, legend cell align={left},
at={(0.01,0.999)},anchor=north west,nodes={scale=0.8}}, legend cell align={left},
%\addlegendentry{Probabilistic truss decomposition by \\ $h$-index based updating,Probabilistic truss decomposition by edge peeling},
%legend entries={Probabilistic truss decomposition by $h$-index based updating,Probabilistic truss decomposition by edge peeling},
%legend entries={PN\_$\text{GB}_1$,PN\_$\text{GB}_2$, PN, PN},
%legend entries={{GB$_1$-$(k,\theta)$-nucleus},{GB$_2$-$(k,\theta)$-nucleus},{$(k,\theta)$-nucleus}},
legend entries={{$\g$-$(k,\theta)$-nucleus}, {$\w$-$(k,\theta)$-nucleus},{$\l$-$(k,\theta)$-nucleus}},
enlarge y limits  = 0.3,
%ymin = 100,
ytick align=inside,
ytick distance =0.2,
xtick style={draw=none},
%legend style={at={(0.5,-0.2)},
%anchor=north,legend columns=-1},
%reverse legend,el pos = near coords,
ymax = 1,
%ticklabel style = {font=\tiny},
ylabel near ticks,
ylabel style={font=\fontsize{6.5}{6}\selectfont},
symbolic x coords={krogan, flickr,dblp},
%xlabel={\textbf{(Datasets, $\eta =0.1$)}},
xlabel style = {font=\fontsize{6.5}{6}\selectfont},
x tick label style={/pgf/number format/1000 sep=},
%ticklabel style = {font=\tiny},
ticklabel style = {font=\fontsize{6}{6}\selectfont},
%nodes near coords,
every node near coord/.append style={align=left, rotate=60, anchor=west,font=\fontsize{6}{6}\selectfont},
point meta=rawy,
%nodes near coords align={horizontal},
%nodes near coords style={rotate=90},
%x tick label style={rotate=45,anchor=east},

%\addlegendentry{Probabilistic truss}
\addplot[fill = red] coordinates {
(krogan,0.72) (dblp, 0.61) (flickr, 0.57)
%(krogan,8.899) (flickr, 1476) (dblp,10076)
%\addlegendentry{Probabilistic truss}
\addplot[fill = blue ] coordinates {
(krogan,0.66) (dblp, 0.5) (flickr, 0.49)
%(krogan,8.899) (flickr, 1476) (dblp,10076)
\addplot[fill = green] coordinates {
%(krogan,1.707) (flickr, 70.364)
(krogan, 0.6) (flickr, 0.4) (dblp,0.299)
% (krogan,2) (flickr, 76) (dblp, 602) (biomine,4492) (pokec,16895) (ljournal-2008,34978)

%\legend{Probabilistic truss decomposition by $h$-index\_based updating, Probabilistic truss decomposition by edge peeling }
\end{axis}
\end{tikzpicture}
\subfloat{
\begin{tikzpicture}
%[width=6.3cm, xlabel near ticks, ylabel near ticks, name = plot4, title={$\eta = 0.3$}, every axis title/.style={below right,at={(0.3,0.98)}}, legend style={draw=yellow, at={(0.98,0.98)},anchor=north east,nodes={scale=0.5}},xmode=normal,ymode=log,legend entries={dblp, flickr, biomine, cnr-2000, arabic-2005, uk-2005, ljournal-2008, twitter-2010},
%reverse legend, xlabel=Iteration,%ytick align=outside
%  ticklabel style = {font=\tiny},nodes near coords align=horizontal]
\begin{axis}[
%bar width = 0.2cm,
bar width = 0.1cm,
legend style={font=\fontsize{6}{6}\selectfont,%font=\small,
draw = none, %at={(0.85,0.999)},anchor=north east,nodes={scale=0.8}}, legend cell align={left},
at={(0.01,0.999)},anchor=north west,nodes={scale=0.8}}, legend cell align={left},
%\addlegendentry{Probabilistic truss decomposition by \\ $h$-index based updating,Probabilistic truss decomposition by edge peeling},
%legend entries={Probabilistic truss decomposition by $h$-index based updating,Probabilistic truss decomposition by edge peeling},
%legend entries={PN\_$\text{GB}_1$,PN\_$\text{GB}_2$,PN },
%legend entries={{GB$_1$-$(k,\theta)$-nucleus},{GB$_2$-$(k,\theta)$-nucleus},{$(k,\theta)$-nucleus}},
legend entries={{$\g$-$(k,\theta)$-nucleus}, {$\w$-$(k,\theta)$-nucleus},{$\l$-$(k,\theta)$-nucleus}},
enlarge y limits  = 0.3,
%ymin = 0.3,
ymin = 0.4,
%ymin = 100,
ytick align=inside,
ytick distance =0.2,
xtick style={draw=none},
%legend style={at={(0.5,-0.2)},
%anchor=north,legend columns=-1},
%reverse legend,el pos = near coords,
%ymax = 100000,
%ticklabel style = {font=\tiny},
ylabel near ticks,
ylabel style={font=\fontsize{6.5}{6}\selectfont},
symbolic x coords={krogan, flickr,dblp},
%xlabel={\textbf{(Datasets, $\eta =0.1$)}},
xlabel style = {font=\fontsize{6.5}{6}\selectfont},
x tick label style={/pgf/number format/1000 sep=},
%ticklabel style = {font=\tiny},
ticklabel style = {font=\fontsize{6}{6}\selectfont},
%nodes near coords,
every node near coord/.append style={align=left, rotate=60, anchor=west,font=\fontsize{6}{6}\selectfont},
point meta=rawy,
%nodes near coords align={horizontal},
%nodes near coords style={rotate=90},
%x tick label style={rotate=45,anchor=east},

%\addlegendentry{Probabilistic truss}
\addplot[fill = red] coordinates {
(krogan,0.75) (flickr, 0.57) (dblp, 0.612)
%(krogan,8.899) (flickr, 1476) (dblp,10076)
%\addlegendentry{Probabilistic truss}
\addplot[fill = blue] coordinates {
(krogan,0.7) (flickr, 0.48) (dblp, 0.49)
%(krogan,8.899) (flickr, 1476) (dblp,10076)
\addplot[fill = green] coordinates {
%(krogan,1.707) (flickr, 70.364)
(krogan, 0.6) (flickr, 0.4) (dblp,0.32)
% (krogan,2) (flickr, 76) (dblp, 602) (biomine,4492) (pokec,16895) (ljournal-2008,34978)

%\legend{Probabilistic truss decomposition by $h$-index\_based updating, Probabilistic truss decomposition by edge peeling }
\end{axis}
\end{tikzpicture}
\vspace{-0.3cm}
\caption{PD and PCC for $\g$-$\pmb{(k,\theta)}$-nucleus, $\w$-$\pmb{(k,\theta)}$-nucleus, and
%GB$_1$-$(k,\theta)$-nucleus, GB$_2$-$(k,\theta)$-nucleus, and
$\l$-$\pmb{(k,\theta)}$-nucleus on \textit{krogan}, \textit{flickr}, and \textit{dblp}
with $\pmb{\theta = 0.001}$.}
\label{densityglob}
\end{figure}

\smallskip
\noindent
\textbf{Effect of $\epsilon$ and $\delta$.} We consider \textit{krogan} dataset with $\theta=0.1$. The choice of $\epsilon$ and $\delta$ influence the number $n$ of possible worlds we sample. For $\epsilon=0.1$ and $\delta=0.1$ we obtain $n=150$. In order to see the fidelity of our results, we experiment by increasing $n$ to higher values, namely $300, 500, 1000, 2000$. As the results show (please see Table~\ref{epsilondelta}), the following metrics about global and weakly-global nuclei: Average\_PD, Average\_PCC, average number of vertices, and average number of edges change very little.
Specifically, the first two metrics are dispersed by only  on average $0.2\%$ around their mean over the different values of $n$, and the last two metrics are dispersed on average by $1\%$.
There are an infinity of $\epsilon$ and $\delta$ values corresponding to a given sample size; for illustration, for $n=150$, we can have $\epsilon=0.1$, $\delta=0.1$, whereas for $n=2000$, we can have $\epsilon=0.03$ and $\delta=0.05$,
i.e. we see that even though in the latter case the $\epsilon$ and $\delta$ decrease by a factor of 3 and 2, respectively, still the nuclei results in terms of the aforementioned metrics are almost the same.
This validates the choice of $\epsilon$ and $\delta$ to 0.1 since lower values do not offer significant improvement in the quality of results.

\begin{table*}%[htbp]
\centering
\begin{tabular}{lrrrrrrrrrr}
Sample Size & \multicolumn{2}{c}{Average\_PD} & \multicolumn{2}{c}{Average\_PCC} & \multicolumn{2}{c}{Average\_Edge} & \multicolumn{2}{c}{Average\_Vertex} & \multicolumn{1}{l}{$\epsilon$} & \multicolumn{1}{l}{$\delta$} \\
\midrule
\multicolumn{1}{r}{150} & 0.905584 & 0.725782 & 0.902748 & 0.769718 & 12.74418 & 55.63121 & 5.336294 & 11.97163 & 0.1   & 0.1 \\
\multicolumn{1}{r}{300} & 0.906431 & 0.733021 & 0.903221 & 0.772635 & 12.72539 & 52.95973 & 5.334439 & 11.54362 & 0.07  & 0.05 \\
\multicolumn{1}{r}{500} & 0.905669 & 0.728858 & 0.902708 & 0.767049 & 13.00551 & 53.88276 & 5.383062 & 11.70345 & 0.05  & 0.06 \\
\multicolumn{1}{r}{1000} & 0.905166 & 0.725497 & 0.902250 & 0.766499 & 12.82319 & 53.77241 & 5.355856 & 11.74483 & 0.05  & 0.01 \\
\multicolumn{1}{r}{2000} & 0.905618 & 0.727499 & 0.902628 & 0.768399 & 12.78215 & 54.26389 & 5.349749 & 11.79167 & 0.03  & 0.05 \\
\midrule
Average & 0.905694 & 0.728132 & 0.902711 & 0.768860 & 12.81608 & 54.10199 & 5.35188 & 11.75104 &       &  \\
SD    & 0.000458 & 0.003053 & 0.000347 & 0.002452 &    0.112337   & 0.97803 & 0.01962 & 0.154625 &       &  \\
\bottomrule
\end{tabular}%
\caption{Effect of $\epsilon$ and $\delta$ on different average statistics, including average density, clustering coefficient, number of edges and number of vertices for global and weakly-global. The results shown here on krogan dataset with $\theta=0.1$. Observe that standard deviation is not more than 1\% of the average for all columns. For some of the columns SD is much smaller, e.g. for Average\_PD it is only 0.05\%.}
\label{epsilondelta}%
\vspace{-0.9cm}
\end{table*}%

\smallskip
\noindent
\textbf{Overlapping Nuclei.} As discussed in~\cite{sariyuce2017nucleus}, nuclei can have overlap. In fact, they can share edges and vertices. We perform experiments to study overlap sizes on datasets, \textit{krogan}, \textit{flickr}, and \textit{dblp}. In Figure~\ref{overlapsize}, we plot the overlap size for each pair of $(3,4)$-nuclei. In addition, we note that the total number of overlapping nuclei is smaller than the total number of nuclei subgraphs in the input graph. For instance, for \textit{flickr}, the total number of nuclei with overlap is $24$, while the total number of $(3,4)$-nuclei is $692$.

Moreover, the average Jaccard similarities (ratio of the overlap size to the size of the union of the two nuclei) are small, $0.06$, $0.2$, and $0.1$, for  \textit{krogan}, \textit{flickr}, and \textit{dblp}, respectively.
We also perform a detailed analysis of the density of the overlapping nuclei. In terms of density, Figure~\ref{densitydensity} shows the scatter plot of all intersecting nuclei, where nuclei are indexed by density. Corresponding to two intersecting nuclei of density $\alpha < \beta$, there is a point $(\alpha,\beta)$. The Y-axis shows the nucleus with higher density in the pair. There are overlaps between dense regions. There are bioinformatics applications for finding vertices that are present in numerous dense subgraphs~\cite{hu2005mining}. The $(3, 4)$-nuclei provide many such vertices.
\begin{figure}
\centering
\subfloat{
\begin{tikzpicture}
%[width=6.3cm, xlabel near ticks, ylabel near ticks, name = plot4, title={$\eta = 0.3$}, every axis title/.style={below right,at={(0.3,0.98)}}, legend style={draw=yellow, at={(0.98,0.98)},anchor=north east,nodes={scale=0.5}},xmode=normal,ymode=log,legend entries={dblp, flickr, biomine, cnr-2000, arabic-2005, uk-2005, ljournal-2008, twitter-2010},
%reverse legend, xlabel=Iteration,%ytick align=outside
%  ticklabel style = {font=\tiny},nodes near coords align=horizontal]
\begin{axis}[
%bar width = 0.2cm,
bar width = 0.1cm,
legend style={font=\fontsize{6}{6}\selectfont,%font=\small,
draw = none, %at={(0.85,0.999)},anchor=north east,nodes={scale=0.8}}, legend cell align={left},
at={(0.01,0.999)},anchor=north west,nodes={scale=0.8}}, legend cell align={left},
%\addlegendentry{Probabilistic truss decomposition by \\ $h$-index based updating,Probabilistic truss decomposition by edge peeling},
%legend entries={Probabilistic truss decomposition by $h$-index based updating,Probabilistic truss decomposition by edge peeling},
%legend entries={PN\_$\text{GB}_1$,PN\_$\text{GB}_2$, PN, PN},
%legend entries={{GB$_1$-$(k,\theta)$-nucleus},{GB$_2$-$(k,\theta)$-nucleus},{$(k,\theta)$-nucleus}},
%legend entries={{$\g$-$(k,\theta)$-nucleus}, {$\w$-$(k,\theta)$-nucleus},{$\l$-$(k,\theta)$-nucleus}},
enlarge x limits=0.4,
%enlarge y limits  = 0.3,
%ymin = 100,
ytick align=inside,
%ytick distance =0.2,
%xtick distance =1,
xtick style={draw=none},
title style = {font=\fontsize{6.5}{6}\selectfont},
%legend style={at={(0.5,-0.2)},
%anchor=north,legend columns=-1},
%reverse legend,el pos = near coords,
%ymax = 1,
%ticklabel style = {font=\tiny},
xlabel={\textbf{Overlap size}},
ylabel near ticks,
ylabel style={font=\fontsize{6.5}{6}\selectfont},
%symbolic x coords={krogan, flickr,dblp},
%xlabel={\textbf{(Datasets, $\eta =0.1$)}},
xlabel style = {font=\fontsize{6.5}{6}\selectfont},
xtick = {0,1,2,3,4,5,6},
%x tick label style={/pgf/number format/1000 sep=},
%ticklabel style = {font=\tiny},
ticklabel style = {font=\fontsize{6}{6}\selectfont},
%nodes near coords,
every node near coord/.append style={align=left, rotate=60, anchor=west,font=\fontsize{6}{6}\selectfont},
point meta=rawy,
%nodes near coords align={horizontal},
%nodes near coords style={rotate=90},
%x tick label style={rotate=45,anchor=east},

%\addlegendentry{Probabilistic truss}
\addplot[fill = red] coordinates {
(1,141) (2,35) (3,4) (5,1)
\end{axis}
\end{tikzpicture}
\hspace{0.1cm}
\subfloat{
\begin{tikzpicture}
%[width=6.3cm, xlabel near ticks, ylabel near ticks, name = plot4, title={$\eta = 0.3$}, every axis title/.style={below right,at={(0.3,0.98)}}, legend style={draw=yellow, at={(0.98,0.98)},anchor=north east,nodes={scale=0.5}},xmode=normal,ymode=log,legend entries={dblp, flickr, biomine, cnr-2000, arabic-2005, uk-2005, ljournal-2008, twitter-2010},
%reverse legend, xlabel=Iteration,%ytick align=outside
%  ticklabel style = {font=\tiny},nodes near coords align=horizontal]
\begin{axis}[
enlarge x limits=0.4,
%bar width = 0.2cm,
bar width = 0.1cm,
legend style={font=\fontsize{6}{6}\selectfont,%font=\small,
draw = none, %at={(0.85,0.999)},anchor=north east,nodes={scale=0.8}}, legend cell align={left},
at={(0.01,0.999)},anchor=north west,nodes={scale=0.8}}, legend cell align={left},
%\addlegendentry{Probabilistic truss decomposition by \\ $h$-index based updating,Probabilistic truss decomposition by edge peeling},
%legend entries={Probabilistic truss decomposition by $h$-index based updating,Probabilistic truss decomposition by edge peeling},
%legend entries={PN\_$\text{GB}_1$,PN\_$\text{GB}_2$, PN, PN},
%legend entries={{GB$_1$-$(k,\theta)$-nucleus},{GB$_2$-$(k,\theta)$-nucleus},{$(k,\theta)$-nucleus}},
%legend entries={{$\g$-$(k,\theta)$-nucleus}, {$\w$-$(k,\theta)$-nucleus},{$\l$-$(k,\theta)$-nucleus}},
%enlarge y limits  = 0.3,
ymin = 0,
ytick align=inside,
%ytick distance =0.2,
xtick style={draw=none},
title style = {font=\fontsize{6.5}{6}\selectfont},
%legend style={at={(0.5,-0.2)},
%anchor=north,legend columns=-1},
%reverse legend,el pos = near coords,
%ymax = 1,
xtick = {0,1,2,3,4,5,6},
%ticklabel style = {font=\tiny},
xlabel={\textbf{Overlap size}},
ylabel near ticks,
ylabel style={font=\fontsize{6.5}{6}\selectfont},
%symbolic x coords={krogan, flickr,dblp},
%xlabel={\textbf{(Datasets, $\eta =0.1$)}},
xlabel style = {font=\fontsize{6.5}{6}\selectfont},
%x tick label style={/pgf/number format/1000 sep=},
%ticklabel style = {font=\tiny},
ticklabel style = {font=\fontsize{6}{6}\selectfont},
%nodes near coords,
every node near coord/.append style={align=left, rotate=60, anchor=west,font=\fontsize{6}{6}\selectfont},
point meta=rawy,
%nodes near coords align={horizontal},
%nodes near coords style={rotate=90},
%x tick label style={rotate=45,anchor=east},

%\addlegendentry{Probabilistic truss}
\addplot[fill = red] coordinates {
(1,3) (2,16)
\end{axis}
\end{tikzpicture}
\hspace{0.1cm}
\subfloat{
\begin{tikzpicture}
%[width=6.3cm, xlabel near ticks, ylabel near ticks, name = plot4, title={$\eta = 0.3$}, every axis title/.style={below right,at={(0.3,0.98)}}, legend style={draw=yellow, at={(0.98,0.98)},anchor=north east,nodes={scale=0.5}},xmode=normal,ymode=log,legend entries={dblp, flickr, biomine, cnr-2000, arabic-2005, uk-2005, ljournal-2008, twitter-2010},
%reverse legend, xlabel=Iteration,%ytick align=outside
%  ticklabel style = {font=\tiny},nodes near coords align=horizontal]
\begin{axis}[
enlarge x limits=0.4,
%bar width = 0.2cm,
bar width = 0.1cm,
legend style={font=\fontsize{6}{6}\selectfont,%font=\small,
draw = none, %at={(0.85,0.999)},anchor=north east,nodes={scale=0.8}}, legend cell align={left},
at={(0.01,0.999)},anchor=north west,nodes={scale=0.8}}, legend cell align={left},
%\addlegendentry{Probabilistic truss decomposition by \\ $h$-index based updating,Probabilistic truss decomposition by edge peeling},
%legend entries={Probabilistic truss decomposition by $h$-index based updating,Probabilistic truss decomposition by edge peeling},
%legend entries={PN\_$\text{GB}_1$,PN\_$\text{GB}_2$, PN, PN},
%legend entries={{GB$_1$-$(k,\theta)$-nucleus},{GB$_2$-$(k,\theta)$-nucleus},{$(k,\theta)$-nucleus}},
%legend entries={{$\g$-$(k,\theta)$-nucleus}, {$\w$-$(k,\theta)$-nucleus},{$\l$-$(k,\theta)$-nucleus}},
%enlarge y limits  = 0.3,
ymin = 0,
ytick align=inside,
%ytick distance =0.2,
xtick style={draw=none},
title style = {font=\fontsize{6.5}{6}\selectfont},
%legend style={at={(0.5,-0.2)},
%anchor=north,legend columns=-1},
%reverse legend,el pos = near coords,
%ymax = 1,
%ticklabel style = {font=\tiny},
xlabel={\textbf{Overlap size}},
xtick = {0,1,2,3,4,5,6},
ylabel near ticks,
ylabel style={font=\fontsize{6.5}{6}\selectfont},
%symbolic x coords={krogan, flickr,dblp},
%xlabel={\textbf{(Datasets, $\eta =0.1$)}},
xlabel style = {font=\fontsize{6.5}{6}\selectfont},
%x tick label style={/pgf/number format/1000 sep=},
%ticklabel style = {font=\tiny},
ticklabel style = {font=\fontsize{6}{6}\selectfont},
%nodes near coords,
every node near coord/.append style={align=left, rotate=60, anchor=west,font=\fontsize{6}{6}\selectfont},
point meta=rawy,
%nodes near coords align={horizontal},
%nodes near coords style={rotate=90},
%x tick label style={rotate=45,anchor=east},

%\addlegendentry{Probabilistic truss}
\addplot[fill = red] coordinates {
(1,1401) (2,327) (3,54) (4,6)
\end{axis}
\end{tikzpicture}
\vspace{-0.3cm}
\caption{\small Histograms over non-trivial overlaps for $\l$-$(3, 4)$-nuclei with $\theta = 0.1$. Child-ancestor intersections are omitted. Overlap size is in terms of the number of vertices. Most overlaps are small in size.}
\label{overlapsize}
\end{figure}

\begin{figure*}[htbp]
\centering
\subfloat{
\begin{tikzpicture}
\begin{axis}[width=5cm,
ylabel near ticks, name = plot1, title={\textbf{krogan}}, every axis title/.style={above right,at={(0.35,0.98)}}, legend style={nodes={scale=0.5}, draw=none,
at={(0.98,0.98)},anchor=north east},xmode=normal,%ymode=log,
reverse legend, xlabel=\textbf{Density},%ytick align=outside
ylabel style={font=\fontsize{6.5}{6}\selectfont},
title style = {font=\fontsize{6.5}{6}\selectfont},
%symbolic x coords={krogan, flickr,dblp},
%xlabel={\textbf{(Datasets, $\eta =0.1$)}},
xlabel style = {font=\fontsize{6.5}{6}\selectfont},
ticklabel style = {font=\tiny},nodes near coords align=horizontal, ylabel=\textbf{Density}]
\addplot[red, only marks, scatter] table [x=krogan2, y=krogan1,, col sep=comma] {density_density.csv};
%\addplot[blue] table [x=Iteration(second), y=Flickr,, col sep=comma] {Book0.1-ave.csv};
%\addplot[teal] table [x=Iteration(third), y=biomine,, col sep=comma] {Book0.1-ave.csv};
%\addplot[cyan] table [x=Iteration(fourth), y=Cnr-2000,, col sep=comma] {Book0.1-ave.csv};
%\addplot[magenta] table [x=Iteration(sixth), y=ljournal-2008,, col sep=comma] {Book0.1-ave.csv};
\end{axis}
\end{tikzpicture}
\hspace{0.1cm}
\subfloat{
\begin{tikzpicture}
\begin{axis}[width=5cm,
ylabel near ticks, name = plot1, title={\textbf{flickr}}, every axis title/.style={above right,at={(0.35,0.98)}}, legend style={nodes={scale=0.5}, draw=none,
at={(0.98,0.98)},anchor=north east},xmode=normal,%ymode=log,
reverse legend, xlabel=\textbf{Density},%ytick align=outside
ylabel style={font=\fontsize{6.5}{6}\selectfont},
title style = {font=\fontsize{6.5}{6}\selectfont},
%symbolic x coords={krogan, flickr,dblp},
%xlabel={\textbf{(Datasets, $\eta =0.1$)}},
xlabel style = {font=\fontsize{6.5}{6}\selectfont},
ticklabel style = {font=\tiny},nodes near coords align=horizontal, ylabel=\textbf{Density}]
\addplot[cyan, only marks, scatter] table [x=flickr2, y=flickr1,, col sep=comma] {density_density.csv};
%\addplot[blue] table [x=Iteration(second), y=Flickr,, col sep=comma] {Book0.1-ave.csv};
%\addplot[teal] table [x=Iteration(third), y=biomine,, col sep=comma] {Book0.1-ave.csv};
%\addplot[cyan] table [x=Iteration(fourth), y=Cnr-2000,, col sep=comma] {Book0.1-ave.csv};
%\addplot[magenta] table [x=Iteration(sixth), y=ljournal-2008,, col sep=comma] {Book0.1-ave.csv};
\end{axis}
\end{tikzpicture}
\hspace{0.1cm}
\subfloat{
\begin{tikzpicture}
\begin{axis}[width=5cm,
ylabel near ticks, name = plot1, title={\textbf{DBLP}}, every axis title/.style={above right,at={(0.35,0.98)}}, legend style={nodes={scale=0.5}, draw=none,
title style = {font=\fontsize{6.5}{6}\selectfont},
at={(0.98,0.98)},anchor=north east},xmode=normal,%ymode=log,
ylabel style={font=\fontsize{6.5}{6}\selectfont},
%symbolic x coords={krogan, flickr,dblp},
%xlabel={\textbf{(Datasets, $\eta =0.1$)}},
xlabel style = {font=\fontsize{6.5}{6}\selectfont},
title style = {font=\fontsize{6.5}{6}\selectfont},
reverse legend, xlabel=\textbf{Density},%ytick align=outside
ticklabel style = {font=\tiny},nodes near coords align=horizontal, ylabel=\textbf{Density}]
\addplot[blue, only marks, scatter] table [x=dblp2, y=dblp1,, col sep=comma] {dblp.csv};
%\addplot[blue] table [x=Iteration(second), y=Flickr,, col sep=comma] {Book0.1-ave.csv};
%\addplot[teal] table [x=Iteration(third), y=biomine,, col sep=comma] {Book0.1-ave.csv};
%\addplot[cyan] table [x=Iteration(fourth), y=Cnr-2000,, col sep=comma] {Book0.1-ave.csv};
%\addplot[magenta] table [x=Iteration(sixth), y=ljournal-2008,, col sep=comma] {Book0.1-ave.csv};
\end{axis}
\end{tikzpicture}
\vspace{-0.2cm}
\caption{Overlap scatter plots for $\l$-$(3, 4)$-nuclei. Each axis shows the edge density of a participating nucleus
in the pairwise overlap. Larger density is shown on the y-axis. The majority of  overlapping nuclei are dense.}
\label{densitydensity}
\end{figure*}

\looseness=-1
\subsection{Case Study} \label{casestudy}
\textbf{Analysis of DBLP Collaboration Network for task-driven team formation.} To show the usefulness of nucleus decomposition in probabilistic graphs, we apply our decomposition algorithms to solve the \textit{task-driven team formation} problem for a DBLP network. In task-driven team formation \cite{bonchi2014core}, we are given a probabilistic graph $ \G^T = (V,E,p^T)$, which is particularly obtained for task $T$. Vertices in $\G^T$ are individuals and edge probabilities are obtained with respect to task $T$ as described in~\cite{bonchi2014core}.
Given a query $\langle Q,T \rangle$, where $Q \subset V$, and $T$ is a set of keywords describing a task, the goal is to find a set of vertices that contain $Q$ and make a good team to perform the task described by the keywords in $T$.
By a good team we mean a good affinity among the team members in terms of collaboration for the given task~\cite{bonchi2014core}.
%%%Originally, the problem is specified with respect to probabilistic core~\cite{bonchi2014core}.
To solve task-driven team formation using nucleus decomposition, we extend the definition of \cite{bonchi2014core} to employ probabilistic nucleus:
Given a probabilistic graph $\G^T = (V,E,p^T)$ with respect to a task $T$, a query set $Q$ of vertices, and a threshold $\theta$, apply nucleus decomposition on $\G^T$ and find a $(k,\theta)$-nucleus (local/weakly-global/global) which \textbf{(1)} contains the vertices in $Q$, and \textbf{(2)} has the highest value of $k$ for the given $\theta$, and return the obtained subgraph as a solution.

\looseness=-1
In our experiment, we use a DBLP collaboration network from~\cite{bonchi2014core}, where vertices are authors, and edges represent collaboration on at least one paper.
The dataset has $1,089,442$ vertices and $4,144,697$ edges. For each edge, as in \cite{bonchi2014core}, we take the bag of words of the title of all papers coauthored by the two authors connected by the edge and apply Latent Dirichlet Allocation (LDA)~\cite{blei2003latent} to infer its topics and calculate the edge probability.
Given a task $T$ with keywords, and the input collaboration network, we obtain a probabilistic graph $\G^T$, in which the probability of an  edge $(u,v)$ represents the collaboration level in the papers co-authored by $u$ and $v$ related to task $T$~(\cite{bonchi2014core,huang2016truss}).

The first sample query we consider is
\{\mbox{``algorithm''}\},$ \\
$\{\mbox{``Erik\_D.\_Demaine''}$, $\mbox{``J.\_Ian\_Munro''}, \allowdisplaybreaks \mbox{``John\_Iacono''}\}\rangle$. Figure~\ref{taskdrivenex1a} shows the subgraph obtained by $\l$-$(k,\theta)$-nucleus and $\w$-$(k,\theta)$-nucleus decompositions, where $k=2$ and $\theta = 10^{-11}$. As discussed in~\cite{bonchi2014core}, the edge probabilities in the data are very small, which requires setting threshold $\theta$ to a small value. The subgraph contains all the three authors in the query. It has $10$ vertices and $33$ edges. As can be seen, the obtained subgraph is quite good for task-driven team formation. This is because all the authors in the subgraph are well-known and have strong collaboration affinity to work on a research paper related to algorithms. A $\g$-$(k,\theta)$-nucleus (same $k$ and $\theta$) that contains the query vertices is shown with thick blue edges in the same figure. As expected, this subgraph is more cohesive and it happens to be a clique of size $6$. Its density and clustering coefficient is $0.138$ and $0.140$ as opposed to $0.099$ and $0.110$ for the local and weakly-global subgraphs.  From a research perspective the collaborations of the academicians in the blue subgraph are more focused on designing efficient data-structures.

\begin{figure}[h]
\centering
\subfloat[]{\label{taskdrivenex1a}
\includegraphics[scale=0.08]{p5.jpg}
\hspace{0.01cm}
\subfloat[]{\label{taskdrivenex2}
\includegraphics[scale=0.07]{WG3.jpg}
\vspace{-0.1cm}
\caption{\small \textbf{a)} A case study of task-driven team formation with keyword \{``algorithm''\}, and query vertices \{``Erik\_D.\_Demaine'', ``J.\_Ian\_Munro'', ``John\_Iacono''\}, $k=2$, and $\theta = 10^{-11}.$ The depicted graph with thick blue edges corresponds to a $\g$-$(k,\theta)$ nucleus. The whole graph (of 10 vertices) is a $\l$-$(k,\theta)$ nucleus which coincides with a $\w$-$(k,\theta)$ nucleus in this example.
\textbf{b)} A weakly-global $\w$-$(k,\theta)$ nucleus for task-driven team formation with query nodes \{``Xindong\_Wu'', ``Bing\_Liu\_0001'', ``Vipin\_Kumar''\}, and keyword \{ ``algorithm''\}. $k=1$, and $\theta = 10^{-11}.$}
\vspace{-0.1cm}
\end{figure}

\looseness=-1
The second query we use shows the usefulness of the weakly-global notion.
It has keyword \{``algorithm''\} and vertices \{``Xindong\_Wu'',  ``Bing\_Liu\_0001'', ``Vipin\_Kumar''\}.
Figure~\ref{taskdrivenex2} shows the $\w$-$(k,\theta)$ nucleus for this query, where the threshold is the same as before, and $k=1$.
The local nucleus containing the query authors had more than 100 nodes. On the other hand, the global nucleus containing these three query authors was empty.  This example shows that the weakly global notion can discover interesting teams when the other two notions produce teams that are too big or too small (or empty), respectively.

Compared to other notions of dense subgraphs in probabilistic graphs, such as truss decomposition of \cite{huang2016truss}, we observed that our nuclei notions capture denser subgraphs better than the truss counterparts.
For instance, in the example of \cite{huang2016truss} for task-driven query of
\{\mbox{``data'', ``algorithm''},
\{\mbox{``Jeffrey\_D.\_Ullman''},  \mbox{``Piotr\_Indyk''}\}\}
\rangle$, local nucleus gives a smaller community than local truss, namely the community obtained by the global truss:
(``Jeffrey\_D.\_Ullman'', ``Shinji\_Fujiwara'', ``Aristides\_Gionis", ``Rajeev\_Motwani'',\\ ``Mayur\_Datar", ``Edith\_Cohen'', ``Cheng\_Yang'', ``Piotr\_Indyk'').
This is interesting as it shows that, in some cases, communities obtained by the exponential time algorithm of \cite{huang2016truss} for global truss can be obtained by our polynomial time algorithm for local nucleus.

In summary, as shown in this case study, there are cases when we are able to discover good communities with reasonable cohesiveness using only the polynomial time algorithm for local nucleus. However, some local nuclei can be too big. In that case we need to apply the algorithms for weakly-global or global nucleus decomposition using the local nuclei we find (recall that we extract global and weakly-global nuclei from the local nuclei). They usually give smaller and denser communities. When global nuclei are too small or empty, weakly-global nuclei can provide good results.

\section{Related Work}
In this section, we provide an overview of the previous research on dense subgraph mining in deterministic and probabilistic graphs.

In deterministic graphs, core and truss decompositions have been studied in many works~\cite{seidman1983network,huang2014querying,cohen2008trusses,zhang2012extracting,chen2014distributed,chen2016efficient,montresor2012distributed,zhang2016engagement,cheng2011efficient,sariyuce2013streaming,wang2020efficient}.
Core decomposition in probabilistic graphs has been studied in~\cite{bonchi2014core,esfahani2019efficient,peng2018efficient,yang2019index}. Bonchi et al.~\cite{bonchi2014core} were the first to introduce core decomposition for probabilistic graphs. They focus on finding a subgraph in which each vertex is connected to $k$ neighbors within that subgraph with high probability, and find all the probabilistic $k$-cores for different values of $k$.
more efficient algorithms were proposed which can also handle graphs that do not fit in main memory. Recently, a different probabilistic core decomposition model has been studied in~\cite{peng2018efficient}. The authors focus on finding a subgraph which contains nodes with high probability to be $k$-core member in the probabilistic graph.
In~\cite{yang2019index}, an index-based structure is defined for processing core decomposition in probabilistic graphs.
Truss decomposition is another important notion of dense substructures.
In the probabilistic context, the notion of local $(k,\eta)$-truss is introduced by Huang, Lu, and Lakshmanan in \cite{huang2016truss}. The proposed algorithm of~\cite{huang2016truss} for computing local $(k,\eta)$-truss is based on iterative peeling of edges with support less than $k-2$, and updating the support of affected edges. Also, \cite{huang2016truss} proposed the notion of global $(k,\eta)$-truss based on the probability of each edge belonging to a connected $k$-truss in a possible world.
In~\cite{esfahani2019fast}, an approximate algorithm for the local truss decomposition is proposed to efficiently compute the tail probability of edge supports in the peeling process of~\cite{huang2016truss}.

Building on the well-studied notions of core and truss decomposition, Sarıyüce~et~al.~\cite{sariyuce2015finding} introduce nucleus decomposition in \textit{deterministic} graphs. They propose an algorithm for computing $(3,4)$-nuclei.
%, based on the Matula-Beck approach for computing $k$-cores~\cite{matula1983smallest}.
They showed that in practice, $(3,4)$-nuclei decomposition provides the most interesting dense subgraph decomposition for real-world networks. In a more recent work, Sarıyüce~et~al.~\cite{sariyuce2018local} propose efficient distributed algorithms for nucleus decomposition. Their approach uses local information of the graph and computes nucleus decomposition with convergence guarantees.
Our work is the first to study nucleus decomposition in probabilistic graphs. %\textcolor{blue}{
In terms of other research related to querying and mining probabilistic graphs, Maniu et al.~\cite{maniu2017indexing} study the problem of source to target queries over probabilistic graphs.
Ceccarello et al.~\cite{ceccarello2017clustering} propose approximate algorithms for clustering of probabilistic graphs.
Ma et al.~\cite{ma2019linc} extend the problem of motif counting to probabilistic graphs.

%However, methods proposed in core and truss decomposition of probabilistic graphs cannot be directly applied for finding nucleus decomposition in probabilistic context. Nucleus decomposition is much more challenging due to the requirement of working on cliques. In addition, due to small occurrence probability of cliques, this problem should be defined in an appropriate way for probabilistic graphs to achieve the desired results. These imply proposing algorithms which can scale to large graphs and can produce accurate results when probabilities become small.

\section{Conclusions}
In this work, we made several key contributions. We  introduced the notion of local, weakly-global and global nuclei for probabilistic graphs. We showed that computing weakly-global and global nuclei is intractable. We complemented these hardness results with effective algorithms to approximate them using techniques from Monte-Carlo sampling.

We designed a polynomial time, peeling based algorithm for computing local nuclei based on dynamic programming and showed that its efficiency can be much improved using novel approximations based on Poisson, Binomial and Normal distributions. Finally, using an in-depth experimental study, we demonstrated the efficiency, scalability and accuracy of our algorithms for nucleus decomposition on real world datasets.

\balance
\bibliographystyle{ACM-Reference-Format}
%%% -*-BibTeX-*-
%%% Do NOT edit. File created by BibTeX with style
%%% ACM-Reference-Format-Journals [18-Jan-2012].

\begin{thebibliography}{59}

%%% ====================================================================
%%% NOTE TO THE USER: you can override these defaults by providing
%%% customized versions of any of these macros before the \bibliography
%%% command.  Each of them MUST provide its own final punctuation,
%%% except for \shownote{}, \showDOI{}, and \showURL{}.  The latter two
%%% do not use final punctuation, in order to avoid confusing it with
%%% the Web address.
%%% To suppress output of a particular field, define its macro to expand
%%% to an empty string, or better, \unskip, like this:
%%% \newcommand{\showDOI}[1]{\unskip}   % LaTeX syntax
%%% \def \showDOI #1{\unskip}           % plain TeX syntax
%%% ====================================================================

\ifx \showCODEN    \undefined \def \showCODEN     #1{\unskip}     \fi
\ifx \showDOI      \undefined \def \showDOI       #1{#1}\fi
\ifx \showISBNx    \undefined \def \showISBNx     #1{\unskip}     \fi
\ifx \showISBNxiii \undefined \def \showISBNxiii  #1{\unskip}     \fi
\ifx \showISSN     \undefined \def \showISSN      #1{\unskip}     \fi
\ifx \showLCCN     \undefined \def \showLCCN      #1{\unskip}     \fi
\ifx \shownote     \undefined \def \shownote      #1{#1}          \fi
\ifx \showarticletitle \undefined \def \showarticletitle #1{#1}   \fi
\ifx \showURL      \undefined \def \showURL       {\relax}        \fi
% The following commands are used for tagged output and should be
% invisible to TeX
\providecommand\bibfield[2]{#2}
\providecommand\bibinfo[2]{#2}
\providecommand\natexlab[1]{#1}
\providecommand\showeprint[2][]{arXiv:#2}

\bibitem[\protect\citeauthoryear{Antiqueira, Oliveira~Jr, da~Fontoura~Costa,
and Nunes}{Antiqueira et~al\mbox{.}}{2009}]%
\bibfield{author}{\bibinfo{person}{L. Antiqueira}, \bibinfo{person}{O.~N.
Oliveira~Jr}, \bibinfo{person}{L. da Fontoura~Costa}, {and}
\bibinfo{person}{M.~d. G.~V Nunes}.} \bibinfo{year}{2009}\natexlab{}.
\newblock \showarticletitle{A complex network approach to text summarization}.
\newblock \bibinfo{journal}{\emph{Information Sciences}} \bibinfo{volume}{179},
\bibinfo{number}{5} (\bibinfo{year}{2009}), \bibinfo{pages}{584--599}.
\newblock

\bibitem[\protect\citeauthoryear{Batagelj and Zaver{\v{s}}nik}{Batagelj and
\bibfield{author}{\bibinfo{person}{V. Batagelj} {and} \bibinfo{person}{M.
Zaver{\v{s}}nik}.} \bibinfo{year}{2011}\natexlab{}.
\newblock \showarticletitle{Fast algorithms for determining (generalized) core
groups in social networks}.
\newblock \bibinfo{journal}{\emph{Advances in Data Analysis and
Classification}} \bibinfo{volume}{5}, \bibinfo{number}{2}
(\bibinfo{year}{2011}), \bibinfo{pages}{129--145}.
\newblock

\bibitem[\protect\citeauthoryear{Blei, Ng, and Jordan}{Blei
\bibfield{author}{\bibinfo{person}{David~M Blei}, \bibinfo{person}{Andrew~Y
Ng}, {and} \bibinfo{person}{Michael~I Jordan}.}
\bibinfo{year}{2003}\natexlab{}.
\newblock \showarticletitle{Latent dirichlet allocation}.
\newblock \bibinfo{journal}{\emph{Journal of machine Learning research}}
\bibinfo{volume}{3}, \bibinfo{number}{Jan} (\bibinfo{year}{2003}),
\bibinfo{pages}{993--1022}.
\newblock

\bibitem[\protect\citeauthoryear{Bonchi, Gullo, Kaltenbrunner, and
Volkovich}{Bonchi et~al\mbox{.}}{2014}]%
\bibfield{author}{\bibinfo{person}{F. Bonchi}, \bibinfo{person}{F. Gullo},
\bibinfo{person}{A. Kaltenbrunner}, {and} \bibinfo{person}{Y. Volkovich}.}
\bibinfo{year}{2014}\natexlab{}.
\newblock \showarticletitle{Core decomposition of uncertain graphs}. In
\bibinfo{booktitle}{\emph{Proceedings of the 20th ACM SIGKDD International
Conference on Knowledge Discovery and Data Mining}}.
\bibinfo{publisher}{ACM}, \bibinfo{pages}{1316--1325}.
\newblock

\bibitem[\protect\citeauthoryear{Borgs, Brautbar, Chayes, and Lucier}{Borgs
\bibfield{author}{\bibinfo{person}{Ch. Borgs}, \bibinfo{person}{M. Brautbar},
\bibinfo{person}{J. Chayes}, {and} \bibinfo{person}{B. Lucier}.}
\bibinfo{year}{2014}\natexlab{}.
\newblock \showarticletitle{Maximizing social influence in nearly optimal
time}. In \bibinfo{booktitle}{\emph{Proceedings of the twenty-fifth Annual
ACM-SIAM Symposium on Discrete Algorithms}}. SIAM, \bibinfo{pages}{946--957}.
\newblock

\bibitem[\protect\citeauthoryear{Budak, Agrawal, and El~Abbadi}{Budak
\bibfield{author}{\bibinfo{person}{C. Budak}, \bibinfo{person}{D. Agrawal},
{and} \bibinfo{person}{A. El~Abbadi}.} \bibinfo{year}{2011}\natexlab{}.
\newblock \showarticletitle{Limiting the spread of misinformation in social
networks}. In \bibinfo{booktitle}{\emph{Proceedings of the 20th International
Conference on World Wide Web}}. \bibinfo{pages}{665--674}.
\newblock

\bibitem[\protect\citeauthoryear{Cavallaro}{Cavallaro}{2010}]%
\bibfield{author}{\bibinfo{person}{G. Cavallaro}.}
\bibinfo{year}{2010}\natexlab{}.
\newblock \showarticletitle{Genome-wide analysis of eukaryotic twin CX 9 C
\newblock \bibinfo{journal}{\emph{Molecular BioSystems}} \bibinfo{volume}{6},
\bibinfo{number}{12} (\bibinfo{year}{2010}), \bibinfo{pages}{2459--2470}.
\newblock

\bibitem[\protect\citeauthoryear{Ceccarello, Fantozzi, Pietracaprina, Pucci,
and Vandin}{Ceccarello et~al\mbox{.}}{2017}]%
\bibfield{author}{\bibinfo{person}{Matteo Ceccarello}, \bibinfo{person}{Carlo
Fantozzi}, \bibinfo{person}{Andrea Pietracaprina}, \bibinfo{person}{Geppino
Pucci}, {and} \bibinfo{person}{Fabio Vandin}.}
\bibinfo{year}{2017}\natexlab{}.
\newblock \showarticletitle{Clustering uncertain graphs}.
\newblock \bibinfo{journal}{\emph{Proceedings of the VLDB Endowment}}
\bibinfo{volume}{11}, \bibinfo{number}{4} (\bibinfo{year}{2017}),
\bibinfo{pages}{472--484}.
\newblock

\bibitem[\protect\citeauthoryear{Chen, Chou, and Chen}{Chen
\bibfield{author}{\bibinfo{person}{P.L. Chen}, \bibinfo{person}{Ch.~K. Chou},
{and} \bibinfo{person}{M.S. Chen}.} \bibinfo{year}{2014}\natexlab{}.
\newblock \showarticletitle{Distributed algorithms for k-truss decomposition}.
In \bibinfo{booktitle}{\emph{Proceedings of 2014 IEEE International
Conference on Big Data (Big Data)}}. IEEE, \bibinfo{pages}{471--480}.
\newblock

\bibitem[\protect\citeauthoryear{Chen, Wei, Popova, and Thomo}{Chen
\bibfield{author}{\bibinfo{person}{Shu Chen}, \bibinfo{person}{Ran Wei},
\bibinfo{person}{Diana Popova}, {and} \bibinfo{person}{Alex Thomo}.}
\bibinfo{year}{2016}\natexlab{}.
\newblock \showarticletitle{Efficient computation of importance based
communities in web-scale networks using a single machine}. In
\bibinfo{booktitle}{\emph{Proceedings of the 25th ACM International on
Conference on Information and Knowledge Management}}.
\bibinfo{pages}{1553--1562}.
\newblock

\bibitem[\protect\citeauthoryear{Cheng, Ke, Chu, and {\"O}zsu}{Cheng
\bibfield{author}{\bibinfo{person}{J. Cheng}, \bibinfo{person}{Y. Ke},
\bibinfo{person}{Sh. Chu}, {and} \bibinfo{person}{M.~T. {\"O}zsu}.}
\bibinfo{year}{2011}\natexlab{}.
\newblock \showarticletitle{Efficient core decomposition in massive networks}.
In \bibinfo{booktitle}{\emph{Proceedings of the 2011 IEEE 27th International
Conference on Data Engineering}}. IEEE, \bibinfo{pages}{51--62}.
\newblock

\bibitem[\protect\citeauthoryear{Cohen}{Cohen}{2008}]%
\bibfield{author}{\bibinfo{person}{J. Cohen}.} \bibinfo{year}{2008}\natexlab{}.
\newblock \showarticletitle{Trusses: Cohesive subgraphs for social network
\newblock \bibinfo{journal}{\emph{National security agency technical report}}
\bibinfo{volume}{16} (\bibinfo{year}{2008}), \bibinfo{pages}{3--1}.
\newblock

\bibitem[\protect\citeauthoryear{Dittrich, Klau, Rosenwald, Dandekar, and
M{\"u}ller}{Dittrich et~al\mbox{.}}{2008}]%
\bibfield{author}{\bibinfo{person}{M.~T. Dittrich}, \bibinfo{person}{G.~W.
Klau}, \bibinfo{person}{A. Rosenwald}, \bibinfo{person}{T. Dandekar}, {and}
\bibinfo{person}{T. M{\"u}ller}.} \bibinfo{year}{2008}\natexlab{}.
\newblock \showarticletitle{Identifying functional modules in protein--protein
interaction networks: an integrated exact approach}.
\newblock \bibinfo{journal}{\emph{Bioinformatics}} \bibinfo{volume}{24},
\bibinfo{number}{13} (\bibinfo{year}{2008}), \bibinfo{pages}{i223--i231}.
\newblock

\bibitem[\protect\citeauthoryear{Dong and Horvath}{Dong and Horvath}{2007}]%
\bibfield{author}{\bibinfo{person}{J. Dong} {and} \bibinfo{person}{S.
Horvath}.} \bibinfo{year}{2007}\natexlab{}.
\newblock \showarticletitle{Understanding network concepts in modules}.
\newblock \bibinfo{journal}{\emph{BMC systems biology}} \bibinfo{volume}{1},
\bibinfo{number}{1} (\bibinfo{year}{2007}), \bibinfo{pages}{24}.
\newblock

\bibitem[\protect\citeauthoryear{Dourisboure, Geraci, and
Pellegrini}{Dourisboure et~al\mbox{.}}{2007}]%
\bibfield{author}{\bibinfo{person}{Y. Dourisboure}, \bibinfo{person}{F.
Geraci}, {and} \bibinfo{person}{M. Pellegrini}.}
\bibinfo{year}{2007}\natexlab{}.
\newblock \showarticletitle{Extraction and classification of dense communities
in the web}. In \bibinfo{booktitle}{\emph{Proceedings of the 16th
International Conference on World Wide Web}}. ACM, \bibinfo{pages}{461--470}.
\newblock

\bibitem[\protect\citeauthoryear{Ehm}{Ehm}{1991}]%
\bibfield{author}{\bibinfo{person}{W. Ehm}.} \bibinfo{year}{1991}\natexlab{}.
\newblock \showarticletitle{Binomial approximation to the Poisson binomial
\newblock \bibinfo{journal}{\emph{Statistics \& Probability Letters}}
\bibinfo{volume}{11}, \bibinfo{number}{1} (\bibinfo{year}{1991}),
\bibinfo{pages}{7--16}.
\newblock

\bibitem[\protect\citeauthoryear{Esfahani, Srinivasan, Thomo, and Wu}{Esfahani
\bibfield{author}{\bibinfo{person}{F. Esfahani}, \bibinfo{person}{V.
Srinivasan}, \bibinfo{person}{A. Thomo}, {and} \bibinfo{person}{K. Wu}.}
\bibinfo{year}{2019}\natexlab{a}.
\newblock \showarticletitle{Efficient Computation of Probabilistic Core
Decomposition at Web-Scale.}. In \bibinfo{booktitle}{\emph{Proceedings of the
22nd International Conference on Extending Database Technology (EDBT)}}.
\bibinfo{pages}{325--336}.
\newblock

\bibitem[\protect\citeauthoryear{Esfahani, Wu, Srinivasan, Thomo, and
Wu}{Esfahani et~al\mbox{.}}{2019b}]%
\bibfield{author}{\bibinfo{person}{Fatemeh Esfahani}, \bibinfo{person}{Jian
Wu}, \bibinfo{person}{Venkatesh Srinivasan}, \bibinfo{person}{Alex Thomo},
{and} \bibinfo{person}{Kui Wu}.} \bibinfo{year}{2019}\natexlab{b}.
\newblock \showarticletitle{Fast Truss Decomposition in Large-scale
Probabilistic Graphs.}. In \bibinfo{booktitle}{\emph{Proceedings of the 22nd
International Conference on Extending Database Technology (EDBT)}}.
\bibinfo{pages}{722--725}.
\newblock

\bibitem[\protect\citeauthoryear{Fratkin, Naughton, Brutlag, and
Batzoglou}{Fratkin et~al\mbox{.}}{2006}]%
\bibfield{author}{\bibinfo{person}{E. Fratkin}, \bibinfo{person}{B.~T.
Naughton}, \bibinfo{person}{D.~L. Brutlag}, {and} \bibinfo{person}{S.
Batzoglou}.} \bibinfo{year}{2006}\natexlab{}.
\newblock \showarticletitle{MotifCut: regulatory motifs finding with maximum
density subgraphs}.
\newblock \bibinfo{journal}{\emph{Bioinformatics}} \bibinfo{volume}{22},
\bibinfo{number}{14} (\bibinfo{year}{2006}), \bibinfo{pages}{e150--e157}.
\newblock

\bibitem[\protect\citeauthoryear{Goyal, Bonchi, and Lakshmanan}{Goyal
\bibfield{author}{\bibinfo{person}{A. Goyal}, \bibinfo{person}{F. Bonchi},
{and} \bibinfo{person}{L.~V.S. Lakshmanan}.} \bibinfo{year}{2010}\natexlab{}.
\newblock \showarticletitle{Learning influence probabilities in social
networks}. In \bibinfo{booktitle}{\emph{Proceedings of the third ACM
International Conference on Web search and Data Mining}}.
\bibinfo{pages}{241--250}.
\newblock

\bibitem[\protect\citeauthoryear{Haight}{Haight}{1967}]%
\bibfield{author}{\bibinfo{person}{F.~A. Haight}.}
\bibinfo{year}{1967}\natexlab{}.
\newblock \showarticletitle{Handbook of the Poisson distribution}.
\newblock  (\bibinfo{year}{1967}).
\newblock

\bibitem[\protect\citeauthoryear{Hoeffding}{Hoeffding}{1994}]%
\bibfield{author}{\bibinfo{person}{W. Hoeffding}.}
\bibinfo{year}{1994}\natexlab{}.
\newblock \showarticletitle{Probability inequalities for sums of bounded random
\newblock In \bibinfo{booktitle}{\emph{The Collected Works of Wassily
Hoeffding}}. \bibinfo{publisher}{Springer}, \bibinfo{pages}{409--426}.
\newblock

\bibitem[\protect\citeauthoryear{Hu, Yan, Huang, Han, and Zhou}{Hu
\bibfield{author}{\bibinfo{person}{Haiyan Hu}, \bibinfo{person}{Xifeng Yan},
\bibinfo{person}{Yu Huang}, \bibinfo{person}{Jiawei Han}, {and}
\bibinfo{person}{Xianghong~Jasmine Zhou}.} \bibinfo{year}{2005}\natexlab{}.
\newblock \showarticletitle{Mining coherent dense subgraphs across massive
biological networks for functional discovery}.
\newblock \bibinfo{journal}{\emph{Bioinformatics}} \bibinfo{volume}{21},
\bibinfo{number}{suppl\_1} (\bibinfo{year}{2005}),
\bibinfo{pages}{i213--i221}.
\newblock

\bibitem[\protect\citeauthoryear{Huang, Cheng, Qin, Tian, and Yu}{Huang
\bibfield{author}{\bibinfo{person}{X. Huang}, \bibinfo{person}{H. Cheng},
\bibinfo{person}{L. Qin}, \bibinfo{person}{W. Tian}, {and}
\bibinfo{person}{J.~X. Yu}.} \bibinfo{year}{2014}\natexlab{}.
\newblock \showarticletitle{Querying k-truss community in large and dynamic
graphs}. In \bibinfo{booktitle}{\emph{Proceedings of the 2014 ACM SIGMOD
International Conference on Management of Data}}.
\bibinfo{pages}{1311--1322}.
\newblock

\bibitem[\protect\citeauthoryear{Huang, Lu, and Lakshmanan}{Huang
\bibfield{author}{\bibinfo{person}{X. Huang}, \bibinfo{person}{W. Lu}, {and}
\bibinfo{person}{L.~V. Lakshmanan}.} \bibinfo{year}{2016}\natexlab{}.
\newblock \showarticletitle{Truss decomposition of probabilistic graphs:
Semantics and algorithms}. In \bibinfo{booktitle}{\emph{Proceedings of the
2016 International Conference on Management of Data}}.
\bibinfo{publisher}{ACM}, \bibinfo{pages}{77--90}.
\newblock

\bibitem[\protect\citeauthoryear{Jin, Liu, and Aggarwal}{Jin
\bibfield{author}{\bibinfo{person}{R. Jin}, \bibinfo{person}{L. Liu}, {and}
\bibinfo{person}{Ch. Aggarwal}.} \bibinfo{year}{2011}\natexlab{}.
\newblock \showarticletitle{Discovering highly reliable subgraphs in uncertain
graphs}. In \bibinfo{booktitle}{\emph{Proceedings of the 17th ACM SIGKDD
International Conference on Knowledge Discovery and Data Mining}}. ACM,
\bibinfo{pages}{992--1000}.
\newblock

\bibitem[\protect\citeauthoryear{Kempe, Kleinberg, and Tardos}{Kempe
\bibfield{author}{\bibinfo{person}{D. Kempe}, \bibinfo{person}{J. Kleinberg},
{and} \bibinfo{person}{{\'E}. Tardos}.} \bibinfo{year}{2003}\natexlab{}.
\newblock \showarticletitle{Maximizing the spread of influence through a social
network}. In \bibinfo{booktitle}{\emph{Proceedings of the ninth ACM SIGKDD
International Conference on Knowledge Discovery and Data Mining}}.
\bibinfo{pages}{137--146}.
\newblock

\bibitem[\protect\citeauthoryear{Khaouid, Barsky, Srinivasan, and
Thomo}{Khaouid et~al\mbox{.}}{2015}]%
\bibfield{author}{\bibinfo{person}{Wissam Khaouid}, \bibinfo{person}{Marina
Barsky}, \bibinfo{person}{Venkatesh Srinivasan}, {and} \bibinfo{person}{Alex
Thomo}.} \bibinfo{year}{2015}\natexlab{}.
\newblock \showarticletitle{K-core decomposition of large networks on a single
\newblock \bibinfo{journal}{\emph{Proceedings of the VLDB Endowment}}
\bibinfo{volume}{9}, \bibinfo{number}{1} (\bibinfo{year}{2015}),
\bibinfo{pages}{13--23}.
\newblock

\bibitem[\protect\citeauthoryear{Korovaiko and Thomo}{Korovaiko and
\bibfield{author}{\bibinfo{person}{N. Korovaiko} {and} \bibinfo{person}{A.
Thomo}.} \bibinfo{year}{2013}\natexlab{}.
\newblock \showarticletitle{Trust prediction from user-item ratings}.
\newblock \bibinfo{journal}{\emph{Social Network Analysis and Mining}}
\bibinfo{volume}{3}, \bibinfo{number}{3} (\bibinfo{year}{2013}),
\bibinfo{pages}{749--759}.
\newblock

\bibitem[\protect\citeauthoryear{Krogan, Cagney, Yu, Zhong, Guo, Ignatchenko,
Li, Pu, Datta, Tikuisis, et~al\mbox{.}}{Krogan et~al\mbox{.}}{2006}]%
\bibfield{author}{\bibinfo{person}{N.~J. Krogan}, \bibinfo{person}{G. Cagney},
\bibinfo{person}{H. Yu}, \bibinfo{person}{G. Zhong}, \bibinfo{person}{X.
Guo}, \bibinfo{person}{A. Ignatchenko}, \bibinfo{person}{J. Li},
\bibinfo{person}{Sh. Pu}, \bibinfo{person}{N. Datta}, \bibinfo{person}{A.~P.
Tikuisis}, {et~al\mbox{.}}} \bibinfo{year}{2006}\natexlab{}.
\newblock \showarticletitle{Global landscape of protein complexes in the yeast
Saccharomyces cerevisiae}.
\newblock \bibinfo{journal}{\emph{Nature}} \bibinfo{volume}{440},
\bibinfo{number}{7084} (\bibinfo{year}{2006}), \bibinfo{pages}{637}.
\newblock

\bibitem[\protect\citeauthoryear{Kumar, Raghavan, Rajagopalan, and
Tomkins}{Kumar et~al\mbox{.}}{1999}]%
\bibfield{author}{\bibinfo{person}{R. Kumar}, \bibinfo{person}{P. Raghavan},
\bibinfo{person}{S. Rajagopalan}, {and} \bibinfo{person}{A. Tomkins}.}
\bibinfo{year}{1999}\natexlab{}.
\newblock \showarticletitle{Trawling the Web for emerging cyber-communities}.
\newblock \bibinfo{journal}{\emph{Computer networks}} \bibinfo{volume}{31},
\bibinfo{number}{11-16} (\bibinfo{year}{1999}), \bibinfo{pages}{1481--1493}.
\newblock

\bibitem[\protect\citeauthoryear{Kuter and Golbeck}{Kuter and Golbeck}{2010}]%
\bibfield{author}{\bibinfo{person}{U. Kuter} {and} \bibinfo{person}{J.
Golbeck}.} \bibinfo{year}{2010}\natexlab{}.
\newblock \showarticletitle{Using probabilistic confidence models for trust
inference in web-based social networks}.
\newblock \bibinfo{journal}{\emph{ACM Transactions on Internet Technology
(TOIT)}} \bibinfo{volume}{10}, \bibinfo{number}{2} (\bibinfo{year}{2010}),
\bibinfo{pages}{8}.
\newblock

\bibitem[\protect\citeauthoryear{Le~Cam}{Le~Cam}{1960}]%
\bibfield{author}{\bibinfo{person}{L. Le~Cam}.}
\bibinfo{year}{1960}\natexlab{}.
\newblock \showarticletitle{An approximation theorem for the Poisson binomial
\newblock \bibinfo{journal}{\emph{Pacific J. Math.}} \bibinfo{volume}{10},
\bibinfo{number}{4} (\bibinfo{year}{1960}), \bibinfo{pages}{1181--1197}.
\newblock

\bibitem[\protect\citeauthoryear{Lyapunov}{Lyapunov}{1901}]%
\bibfield{author}{\bibinfo{person}{A. Lyapunov}.}
\bibinfo{year}{1901}\natexlab{}.
\newblock \showarticletitle{Nouvelle forme de la th\'{e}oreme dur la limite de
\newblock \bibinfo{journal}{\emph{M\'{e}moires de l’Academie Imp\'{e}riale
des Sci. de St. Petersbourg}}  \bibinfo{volume}{12} (\bibinfo{year}{1901}),
\bibinfo{pages}{1\--24}.
\newblock

\bibitem[\protect\citeauthoryear{Ma, Cheng, Lakshmanan, Grubenmann, Fang, and
Li}{Ma et~al\mbox{.}}{2019}]%
\bibfield{author}{\bibinfo{person}{Chenhao Ma}, \bibinfo{person}{Reynold
Cheng}, \bibinfo{person}{Laks~VS Lakshmanan}, \bibinfo{person}{Tobias
Grubenmann}, \bibinfo{person}{Yixiang Fang}, {and} \bibinfo{person}{Xiaodong
Li}.} \bibinfo{year}{2019}\natexlab{}.
\newblock \showarticletitle{LINC: a motif counting algorithm for uncertain
\newblock \bibinfo{journal}{\emph{Proceedings of the VLDB Endowment}}
\bibinfo{volume}{13}, \bibinfo{number}{2} (\bibinfo{year}{2019}),
\bibinfo{pages}{155--168}.
\newblock

\bibitem[\protect\citeauthoryear{Maniu, Cheng, and Senellart}{Maniu
\bibfield{author}{\bibinfo{person}{Silviu Maniu}, \bibinfo{person}{Reynold
Cheng}, {and} \bibinfo{person}{Pierre Senellart}.}
\bibinfo{year}{2017}\natexlab{}.
\newblock \showarticletitle{An indexing framework for queries on probabilistic
\newblock \bibinfo{journal}{\emph{ACM Transactions on Database Systems (TODS)}}
\bibinfo{volume}{42}, \bibinfo{number}{2} (\bibinfo{year}{2017}),
\bibinfo{pages}{1--34}.
\newblock

\bibitem[\protect\citeauthoryear{Montresor, De~Pellegrini, and
Miorandi}{Montresor et~al\mbox{.}}{2012}]%
\bibfield{author}{\bibinfo{person}{A. Montresor}, \bibinfo{person}{F.
De~Pellegrini}, {and} \bibinfo{person}{D. Miorandi}.}
\bibinfo{year}{2012}\natexlab{}.
\newblock \showarticletitle{Distributed k-core decomposition}.
\newblock \bibinfo{journal}{\emph{IEEE Transactions on parallel and distributed
systems}} \bibinfo{volume}{24}, \bibinfo{number}{2} (\bibinfo{year}{2012}),
\bibinfo{pages}{288--300}.
\newblock

\bibitem[\protect\citeauthoryear{Mukherjee, Xu, and Tirthapura}{Mukherjee
\bibfield{author}{\bibinfo{person}{Arko~Provo Mukherjee}, \bibinfo{person}{Pan
Xu}, {and} \bibinfo{person}{Srikanta Tirthapura}.}
\bibinfo{year}{2015}\natexlab{}.
\newblock \showarticletitle{Mining maximal cliques from an uncertain graph}. In
\bibinfo{booktitle}{\emph{2015 IEEE 31st International Conference on Data
Engineering}}. IEEE, \bibinfo{pages}{243--254}.
\newblock

\bibitem[\protect\citeauthoryear{Mukhopadhyay}{Mukhopadhyay}{2000}]%
\bibfield{author}{\bibinfo{person}{Nitis Mukhopadhyay}.}
\bibinfo{year}{2000}\natexlab{}.
\newblock \bibinfo{booktitle}{\emph{Probability and statistical inference}}.
\newblock \bibinfo{publisher}{CRC Press}.
\newblock

\bibitem[\protect\citeauthoryear{Papoulis and Pillai}{Papoulis and
\bibfield{author}{\bibinfo{person}{A. Papoulis} {and} \bibinfo{person}{S.~U.
Pillai}.} \bibinfo{year}{2002}\natexlab{}.
\newblock \bibinfo{booktitle}{\emph{Probability, random variables, and
stochastic processes}}.
\newblock \bibinfo{publisher}{Tata McGraw-Hill Education}.
\newblock

\bibitem[\protect\citeauthoryear{Peng, Zhang, Zhang, Lin, and Qin}{Peng
\bibfield{author}{\bibinfo{person}{Y. Peng}, \bibinfo{person}{Y. Zhang},
\bibinfo{person}{W. Zhang}, \bibinfo{person}{X. Lin}, {and}
\bibinfo{person}{L. Qin}.} \bibinfo{year}{2018}\natexlab{}.
\newblock \showarticletitle{Efficient probabilistic k-core computation on
uncertain graphs}. In \bibinfo{booktitle}{\emph{Proceedings of the IEEE 34th
International Conference on Data Engineering (ICDE)}}. IEEE,
\bibinfo{pages}{1192--1203}.
\newblock

\bibitem[\protect\citeauthoryear{Pfeiffer and Neville}{Pfeiffer and
\bibfield{author}{\bibinfo{person}{J.~J. Pfeiffer} {and} \bibinfo{person}{J.
Neville}.} \bibinfo{year}{2011}\natexlab{}.
\newblock \showarticletitle{Methods to determine node centrality and clustering
in graphs with uncertain structure}. In \bibinfo{booktitle}{\emph{Fifth
International AAAI Conference on Weblogs and Social Media}}.
\newblock

\bibitem[\protect\citeauthoryear{Potamias, Bonchi, Gionis, and
Kollios}{Potamias et~al\mbox{.}}{2010}]%
\bibfield{author}{\bibinfo{person}{M. Potamias}, \bibinfo{person}{F. Bonchi},
\bibinfo{person}{A. Gionis}, {and} \bibinfo{person}{G. Kollios}.}
\bibinfo{year}{2010}\natexlab{}.
\newblock \showarticletitle{K-nearest neighbors in uncertain graphs}.
\newblock \bibinfo{journal}{\emph{PVLDB}} \bibinfo{volume}{3},
\bibinfo{number}{1-2} (\bibinfo{year}{2010}), \bibinfo{pages}{997--1008}.
\newblock

\bibitem[\protect\citeauthoryear{R{\"o}llin}{R{\"o}llin}{2007}]%
\bibfield{author}{\bibinfo{person}{A. R{\"o}llin}.}
\bibinfo{year}{2007}\natexlab{}.
\newblock \showarticletitle{Translated Poisson approximation using exchangeable
pair couplings}.
\newblock \bibinfo{journal}{\emph{The Annals of Applied Probability}}
\bibinfo{volume}{17}, \bibinfo{number}{5/6} (\bibinfo{year}{2007}),
\bibinfo{pages}{1596--1614}.
\newblock

\bibitem[\protect\citeauthoryear{Sariy{\"u}ce, Seshadhri, and
Pinar}{Sariy{\"u}ce et~al\mbox{.}}{2018}]%
\bibfield{author}{\bibinfo{person}{A.E. Sariy{\"u}ce}, \bibinfo{person}{C.
Seshadhri}, {and} \bibinfo{person}{A. Pinar}.}
\bibinfo{year}{2018}\natexlab{}.
\newblock \showarticletitle{Local algorithms for hierarchical dense subgraph
\newblock \bibinfo{journal}{\emph{Proceedings of the VLDB Endowment}}
\bibinfo{volume}{12}, \bibinfo{number}{1} (\bibinfo{year}{2018}),
\bibinfo{pages}{43--56}.
\newblock

\bibitem[\protect\citeauthoryear{Sar{\'\i}y{\"u}ce, Gedik, Jacques-Silva, Wu,
and {\c{C}}ataly{\"u}rek}{Sar{\'\i}y{\"u}ce et~al\mbox{.}}{2013}]%
\bibfield{author}{\bibinfo{person}{A.~E. Sar{\'\i}y{\"u}ce},
\bibinfo{person}{B. Gedik}, \bibinfo{person}{G. Jacques-Silva},
\bibinfo{person}{K.~L. Wu}, {and} \bibinfo{person}{{\"U}.~V.
{\c{C}}ataly{\"u}rek}.} \bibinfo{year}{2013}\natexlab{}.
\newblock \showarticletitle{Streaming algorithms for k-core decomposition}.
\newblock \bibinfo{journal}{\emph{Proceedings of the VLDB Endowment}}
\bibinfo{volume}{6}, \bibinfo{number}{6} (\bibinfo{year}{2013}),
\bibinfo{pages}{433--444}.
\newblock

\bibitem[\protect\citeauthoryear{Sariyuce, Seshadhri, Pinar, and
Catalyurek}{Sariyuce et~al\mbox{.}}{2015}]%
\bibfield{author}{\bibinfo{person}{A.~E. Sariyuce}, \bibinfo{person}{C.
Seshadhri}, \bibinfo{person}{A. Pinar}, {and} \bibinfo{person}{U.~V.
Catalyurek}.} \bibinfo{year}{2015}\natexlab{}.
\newblock \showarticletitle{Finding the hierarchy of dense subgraphs using
nucleus decompositions}. In \bibinfo{booktitle}{\emph{Proceedings of the 24th
International Conference on World Wide Web}}. \bibinfo{pages}{927--937}.
\newblock

\bibitem[\protect\citeauthoryear{Sariy{\"u}ce, Seshadhri, Pinar, and
{\c{C}}ataly{\"u}rek}{Sariy{\"u}ce et~al\mbox{.}}{2017}]%
\bibfield{author}{\bibinfo{person}{Ahmet~Erdem Sariy{\"u}ce},
\bibinfo{person}{C Seshadhri}, \bibinfo{person}{Ali Pinar}, {and}
\bibinfo{person}{{\"U}mit~V {\c{C}}ataly{\"u}rek}.}
\bibinfo{year}{2017}\natexlab{}.
\newblock \showarticletitle{Nucleus decompositions for identifying hierarchy of
dense subgraphs}.
\newblock \bibinfo{journal}{\emph{ACM Transactions on the Web (TWEB)}}
\bibinfo{volume}{11}, \bibinfo{number}{3} (\bibinfo{year}{2017}),
\bibinfo{pages}{1--27}.
\newblock

\bibitem[\protect\citeauthoryear{Seidman}{Seidman}{1983}]%
\bibfield{author}{\bibinfo{person}{S.~B. Seidman}.}
\bibinfo{year}{1983}\natexlab{}.
\newblock \showarticletitle{Network structure and minimum degree}.
\newblock \bibinfo{journal}{\emph{Social networks}} \bibinfo{volume}{5},
\bibinfo{number}{3} (\bibinfo{year}{1983}), \bibinfo{pages}{269--287}.
\newblock

\bibitem[\protect\citeauthoryear{Sharan, Ulitsky, and Shamir}{Sharan
\bibfield{author}{\bibinfo{person}{R. Sharan}, \bibinfo{person}{I. Ulitsky},
{and} \bibinfo{person}{R. Shamir}.} \bibinfo{year}{2007}\natexlab{}.
\newblock \showarticletitle{Network-based prediction of protein function}.
\newblock \bibinfo{journal}{\emph{Molecular systems biology}}
\bibinfo{volume}{3}, \bibinfo{number}{1} (\bibinfo{year}{2007}),
\bibinfo{pages}{88}.
\newblock

\bibitem[\protect\citeauthoryear{Tang, Xiao, and Shi}{Tang
\bibfield{author}{\bibinfo{person}{Y. Tang}, \bibinfo{person}{X. Xiao}, {and}
\bibinfo{person}{Y. Shi}.} \bibinfo{year}{2014}\natexlab{}.
\newblock \showarticletitle{Influence maximization: Near-optimal time
complexity meets practical efficiency}. In
\bibinfo{booktitle}{\emph{Proceedings of the 2014 ACM SIGMOD International
Conference on Management of Data}}. \bibinfo{pages}{75--86}.
\newblock

\bibitem[\protect\citeauthoryear{Valiant}{Valiant}{1979}]%
\bibfield{author}{\bibinfo{person}{L.~G. Valiant}.}
\bibinfo{year}{1979}\natexlab{}.
\newblock \showarticletitle{The complexity of enumeration and reliability
\newblock \bibinfo{journal}{\emph{SIAM J. Comput.}} \bibinfo{volume}{8},
\bibinfo{number}{3} (\bibinfo{year}{1979}), \bibinfo{pages}{410--421}.
\newblock

\bibitem[\protect\citeauthoryear{Wang and Cheng}{Wang and Cheng}{2012}]%
\bibfield{author}{\bibinfo{person}{Jia Wang} {and} \bibinfo{person}{James
Cheng}.} \bibinfo{year}{2012}\natexlab{}.
\newblock \showarticletitle{Truss Decomposition in Massive Networks}.
\newblock \bibinfo{journal}{\emph{Proceedings of the VLDB Endowment}}
\bibinfo{volume}{5}, \bibinfo{number}{9} (\bibinfo{year}{2012}).
\newblock

\bibitem[\protect\citeauthoryear{Wang, Lin, Qin, Zhang, and Zhang}{Wang
\bibfield{author}{\bibinfo{person}{K. Wang}, \bibinfo{person}{X. Lin},
\bibinfo{person}{L. Qin}, \bibinfo{person}{W. Zhang}, {and}
\bibinfo{person}{Y. Zhang}.} \bibinfo{year}{2020}\natexlab{}.
\newblock \showarticletitle{Efficient bitruss decomposition for large-scale
bipartite graphs}. In \bibinfo{booktitle}{\emph{Proceedings of 2020 IEEE 36th
International Conference on Data Engineering (ICDE)}}. IEEE,
\bibinfo{pages}{661--672}.
\newblock

\bibitem[\protect\citeauthoryear{Yang, Wen, Qin, Zhang, Chang, and Li}{Yang
\bibfield{author}{\bibinfo{person}{B. Yang}, \bibinfo{person}{D. Wen},
\bibinfo{person}{L. Qin}, \bibinfo{person}{Y. Zhang}, \bibinfo{person}{L.
Chang}, {and} \bibinfo{person}{R. Li}.} \bibinfo{year}{2019}\natexlab{}.
\newblock \showarticletitle{Index-based Optimal Algorithm for Computing K-Cores
in Large Uncertain Graphs}. In \bibinfo{booktitle}{\emph{Proceedings of the
IEEE 35th International Conference on Data Engineering (ICDE)}}. IEEE,
\bibinfo{pages}{64--75}.
\newblock

\bibitem[\protect\citeauthoryear{Zhang and Horvath}{Zhang and Horvath}{2005}]%
\bibfield{author}{\bibinfo{person}{B. Zhang} {and} \bibinfo{person}{S.
Horvath}.} \bibinfo{year}{2005}\natexlab{}.
\newblock \showarticletitle{A general framework for weighted gene co-expression
network analysis}.
\newblock \bibinfo{journal}{\emph{Statistical applications in genetics and
molecular biology}} \bibinfo{volume}{4}, \bibinfo{number}{1}
\newblock

\bibitem[\protect\citeauthoryear{Zhang, Zhang, Qin, Zhang, and Lin}{Zhang
\bibfield{author}{\bibinfo{person}{Fan Zhang}, \bibinfo{person}{Ying Zhang},
\bibinfo{person}{Lu Qin}, \bibinfo{person}{Wenjie Zhang}, {and}
\bibinfo{person}{Xuemin Lin}.} \bibinfo{year}{2017}\natexlab{}.
\newblock \showarticletitle{When Engagement Meets Similarity: Efficient
(k,r)-Core Computation on Social Networks}.
\newblock \bibinfo{journal}{\emph{Proc. VLDB Endow.}} \bibinfo{volume}{10},
\bibinfo{number}{10} (\bibinfo{year}{2017}), \bibinfo{pages}{998–1009}.
\newblock

\bibitem[\protect\citeauthoryear{Zhang and Parthasarathy}{Zhang and
\bibfield{author}{\bibinfo{person}{Y. Zhang} {and} \bibinfo{person}{S.
Parthasarathy}.} \bibinfo{year}{2012}\natexlab{}.
\newblock \showarticletitle{Extracting analyzing and visualizing triangle
k-core motifs within networks}. In \bibinfo{booktitle}{\emph{Proceedings of
IEEE 28th International Conference on Data Engineering}}. IEEE,
\bibinfo{pages}{1049--1060}.
\newblock

\bibitem[\protect\citeauthoryear{Zhao and Tung}{Zhao and Tung}{2012}]%
\bibfield{author}{\bibinfo{person}{F. Zhao} {and} \bibinfo{person}{A. Tung}.}
\bibinfo{year}{2012}\natexlab{}.
\newblock \showarticletitle{Large scale cohesive subgraphs discovery for social
network visual analysis}.
\newblock \bibinfo{journal}{\emph{Proceedings of the VLDB Endowment}}
\bibinfo{volume}{6} (\bibinfo{year}{2012}), \bibinfo{pages}{85--96}.
\newblock

\end{thebibliography}

\end{document}
\endinput

\begin{defn}
%Let $\S$ be a set of $s$-cliques in $G$.
We define the following notions.
\begin{itemize}
\item $K_r(\S)$: The set of $r$-cliques $R$ for which there exists an $s$-clique $S\in \S$ that contains $R$.
\item $\S\mbox{-degree}$
(or $\S\mbox{-degree}_{G}$)
of $R \in K_r(\S) $: The number of $s$-cliques $S \in \S$ that contain $R$.
\item Two $r$-cliques $R$ and $R'$, are $\S$-connected, if there exists a sequence $R = R_1,R_2,\cdots,R_k=R'$ in $K_r(\S)$ such that for each $i$, some $S \in \S$ contains $R_i \cup R_{i+1}$.
\end{itemize}
\end{defn}

on integer values in
$[0,c_{\t}]$, where  $c_{\t} = \left | N(u) \cap N(v) \cap N(w) \right |$, with different probabilities. T
his gives the probability distribution for the $\S\text{-}\textit{degree}$ of $\t$ in the probabilistic graph $\G$, which we refer to as degree distribution of $\t$.

Definition~\ref{local} satisfies the support of each triangle in $\mathcal H$ in a ``local'' sense as follows. Let $\t_1, \t_2$ be two triangles in $\H$.
The set of possible worlds $P_1$ (based on $\mathcal H$)  in which $\t_1$ is contained in at least $k$ 4-cliques does not need to have a relation at all to the set $P_2$ of possible worlds in which $\t_2$ is contained in at least $k$ 4-cliques though both of these sets have a total probability of at least $\theta$.
In other words, the total probability of the worlds in $P_1 \cap P_2$ is less than $\theta$.
For instance, in the above example we can verify that there is only one possible world in $P_1 \cap P_2$, namely the world given in Figure~\ref{exprob1}~(c), which has a probability of 0.21.
Depending on the application, the user could be interested in a more ``global'' satisfaction of triangle support as we define next.

1. Change Def 5 to have Pr(X_G)

2. Remove weakly-global

3. Leave the definition as is, but remove examples.

l< w_f < w