Efficient Truss Maintenance in Evolving Networks
% % author names are typeset in 11pt
which is the default size in the author block %{Rui Zhou{\small $~^{\#1
% You can go ahead and credit any number of authors here
% e.g. one 'row of three' or two rows (consisting of one row of three % and a second row of one
two or three). % % The command \alignauthor (no curly braces needed) should % precede each author name
affiliation/snail-mail address and % e-mail address. Additionally
tag each line of % affiliation/address with \affaddr
and tag the % e-mail address with \email. % % 1st. author % \alignauthor Rui Zhou
%\titlenote{Part of the work was done while the author was visiting Australian National University.
Truss was proposed to study social network data represented by graphs. A $k$-truss of a graph is a cohesive subgraph, in which each edge is contained in at least $k-2$ triangles within the subgraph. While truss has been demonstrated as superior to model the close relationship in social networks and efficient algorithms for finding trusses have been extensively studied, very little attention has been paid to truss maintenance. However, most social networks are evolving networks. It may be infeasible to recompute trusses from scratch from time to time in order to find the up-to-date $k$-trusses in the evolving networks. In this paper, we discuss how to maintain trusses in a graph with dynamic updates. We first discuss a set of properties on maintaining trusses, then propose algorithms on maintaining trusses on edge deletions and insertions, finally, we discuss truss index maintenance. We test the proposed techniques on real datasets. The experiment results show the promise of our work.
ktrussMaintain.tex

% IEEE Paper Template for US-LETTER Page Size (V1)
% Sample Conference Paper using IEEE LaTeX style file for US-LETTER pagesize.
% Copyright (C) 2006-2008 Causal Productions Pty Ltd.
% Permission is granted to distribute and revise this file provided that
% this header remains intact.
%
% REVISION HISTORY
% 20080211 changed some space characters in the title-author block
%
%\documentclass[10pt,conference,letterpaper]{IEEEtran}
\documentclass{sig-alternate}
%\usepackage{times,amsmath,epsfig}
%\usepackage{times}
\usepackage{graphicx}
\usepackage{amssymb,amsmath}
\usepackage{algorithm}
%\usepackage[noend]{algorithmic}
\usepackage{algorithmic}
\usepackage{subfigure}
%

\begin{document}

\title{Efficient Truss Maintenance in Evolving Networks}
%

\iffalse

\author{%
% author names are typeset in 11pt, which is the default size in the author block
%{Rui Zhou{\small $~^{\#1}$}, Chengfei Liu{\small $~^{\#2}$}, Weifa Liang{\small $~^{*3}$}, Jeffrey Xu Yu{\small $~^{+4}$}, Jianxin Li{\small $~^{\#5}$}}%
{Rui Zhou{\small $~^{\#1}$}, Chengfei Liu{\small $~^{\#2}$}, Weifa Liang{\small $~^{*3}$}, Jeffrey Xu Yu{\small $~^{+4}$}}%
% add some space between author names and affils
\vspace{1.6mm}\\
\fontsize{10}{10}\selectfont\itshape
% 20080211 CAUSAL PRODUCTIONS
% separate superscript on following line from affiliation using narrow space
$^{\#}$\,Faculty of Information \& Communication Technologies\\
Swinburne University of Technology, Melbourne, Australia\\
\fontsize{9}{9}\selectfont\ttfamily\upshape
%
% 20080211 CAUSAL PRODUCTIONS
% in the following email addresses, separate the superscript from the email address 
% using a narrow space \,
% the reason is that Acrobat Reader has an option to auto-detect urls and email
% addresses, and make them 'hot'.  Without a narrow space, the superscript is included
% in the email address and corrupts it.
% Also, removed ~ from pre-superscript since it does not seem to serve any purpose
$^{1}$\,rzhou@swin.edu.au\\
$^{2}$\,cliu@swin.edu.au
%$^{5}$\,jianxinli@swin.edu.au

% add some space between email and affil
\vspace{1.2mm}\\
\fontsize{10}{10}\selectfont\rmfamily\itshape
% 20080211 CAUSAL PRODUCTIONS
% separated superscript on following line from affiliation using narrow space \,
$^{*}$\,School of Computer Science\\
Australian National University, Canberra, Australia\\
\fontsize{9}{9}\selectfont\ttfamily\upshape
% 20080211 CAUSAL PRODUCTIONS
% removed ~ from pre-superscript since it does not seem to serve any purpose
$^{3}$\,wliang@anu.edu.com
\vspace{1.2mm}\\
\fontsize{10}{10}\selectfont\rmfamily\itshape
% 20080211 CAUSAL PRODUCTIONS
% separated superscript on following line from affiliation using narrow space \,
$^{+}$\,Department of Systems Engineering and Engineering Management\\
The Chinese University of Hong Kong, Hong Kong, China\\
\fontsize{9}{9}\selectfont\ttfamily\upshape
% 20080211 CAUSAL PRODUCTIONS
% removed ~ from pre-superscript since it does not seem to serve any purpose
$^{4}$\,yu@se.cuhk.edu.hk
}


\fi

\numberofauthors{3}

\author{
% You can go ahead and credit any number of authors here,
% e.g. one 'row of three' or two rows (consisting of one row of three
% and a second row of one, two or three).
%
% The command \alignauthor (no curly braces needed) should
% precede each author name, affiliation/snail-mail address and
% e-mail address. Additionally, tag each line of
% affiliation/address with \affaddr, and tag the
% e-mail address with \email.
%
% 1st. author
%
\alignauthor
Rui Zhou\\
%\titlenote{Part of the work was done while the author was visiting Australian National University.}
       \affaddr{Center for Applied Informatics}\\
       \affaddr{College of Engineering \& Science}\\
       \affaddr{Victoria University}\\
%       \affaddr{Melbourne, VIC 3122, Australia}\\
       \affaddr{Melbourne, Australia}\\
       \email{Rui.Zhou@vu.edu.au}
% 2nd. author\alignauthor
\alignauthor
Chengfei Liu\\
       \affaddr{Faculty of Information and Communication Technologies}\\
       \affaddr{Swinburne University of Technology}\\
%       \affaddr{Melbourne, VIC 3122, Australia}\\
       \affaddr{Melbourne, Australia}\\
       \email{cliu@swin.edu.au}% 3rd. author% 3rd. author
\alignauthor
Jeffrey Xu Yu\\
       \affaddr{Department of Systems Engineering \& Engineering Management}\\
       \affaddr{The Chinese University of Hong Kong}\\
       \affaddr{Hong Kong, China}\\
       \email{yu@se.cuhk.edu.hk}
\and
\alignauthor
Weifa Liang\\
       \affaddr{Research School of Computer Science}\\
       \affaddr{Australian National University}\\
%       \affaddr{Canberra, NSW 2601, Australia}\\
       \affaddr{Canberra, Australia}\\
       \email{wliang@cs.anu.edu.au}
 % use '\and' if you need 'another row' of author names
% 4th. author
% There's nothing stopping you putting the seventh, eighth, etc.
\alignauthor
Yanchun Zhang\\
       \affaddr{Centre for Applied Informatics}\\
       \affaddr{College of Engineering \& Science}\\
       \affaddr{Victoria University}\\
       \affaddr{Melbourne, Australia}\\
%       \affaddr{Canberra, Australia}\\
       \email{Yanchun.Zhang@vu.edu.au}
%\alignauthor
%Jianxin Li\\
%       \affaddr{Faculty of Information and Communication Technologies}\\
%       \affaddr{Swinburne University of Technology}\\
%       \affaddr{Melbourne, VIC 3122, Australia}\\
%       \affaddr{Melbourne, Australia}\\
%       \email{jianxinli@swin.edu.au}
}% author on the opening page (as the 'third row') but






%
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{example}{Example}
\newtheorem{lemma}{Lemma}
\newtheorem{observation}{Observation}
\newtheorem{conjecture}{Conjecture}
%\newdef{definition}{Definition}
\newtheorem{definition}{Definition}

\newcommand{\includeonefigure}[3]
{
\begin{figure}[t]
    \centering
    #1
    \caption{#2}
    \label{#3}
\end{figure}
}

\maketitle

\begin{abstract}
Truss was proposed to study social network data represented by graphs. A $k$-truss of a graph is a cohesive subgraph, in which each edge is contained in at least $k-2$ triangles within the subgraph. While truss has been demonstrated as superior to model the close relationship in social networks and efficient algorithms for finding trusses have been extensively studied, very little attention has been paid to truss maintenance. However, most social networks are evolving networks. It may be infeasible to recompute trusses from scratch from time to time in order to find the up-to-date $k$-trusses in the evolving networks. In this paper, we discuss how to maintain trusses in a graph with dynamic updates. We first discuss a set of properties on maintaining trusses, then propose algorithms on maintaining trusses on edge deletions and insertions, finally, we discuss truss index maintenance. We test the proposed techniques on real datasets. The experiment results show the promise of our work.

\end{abstract}


\section{Introduction}

Truss was proposed by Jonathan Cohen in~\cite{DBLP:journals/web/truss} in 2008 to identify cohesive subgraphs for social network analysis. The motivation originated from social structure is that if two persons are strongly tied, they should share enough common friends. As such, we have the definition of $k$-truss as follows:
\begin{definition}
A $k$-truss in a graph $G=(V,E)$ is a non-trivial\footnote{A trivial graph is not a 2-truss due to this non-trivial condition.} connected subgraph $G_s=(V_s,E_s)$, where each edge in $E_s$ is contained in at least $k-2$ triangles of $G_s$, here $V_s \subseteq V$ and $E_s \subseteq E$.
\end{definition}
Here, an edge $(a,b)$ is contained in $k-2$ triangles in $G_s$ equals that nodes $a$ and $b$ have $k-2$ common neighbors in $G_s$. Usually, we are interested in the maximal $k$-trusses, i.e. the $k$-trusses which are not proper subgraphs of other $k$-trusses, otherwise there may be too many overlapping trusses resulting from nodes combination. 

Consider a social network as a graph, by identifying maximal $k$-trusses, we can identify a set of cohesive groups or communities. The granularity can be adjusted through the setting of $k$. With the identified communities, analysis can be done to extract local information from the communities and follow-up commercial strategies, such as personalized advertising~\cite{DBLP:journals/ijcsa/MeyerBOS11}, viral marketing~\cite{RePEc:ucp:jconrs:v:14:y:1987:i:3:p:350-62}, can then be devised based on collected information. In fact, the problem of finding cohesive subgraphs has been studied for a long time. There are many other models to identify cohesive subgraphs, e.g., clique, n-clique, quasi-clique, n-clan, n-club, k-plex and k-core. Despite many such models have been proposed, to the best of our knowledge, very little attention has been paid to maintaining the cohesive subgraphs in evolving networks. However, real networks are updated frequently. %It is recorded that 700,000 people join Facebook per day~\cite{Facebook}. For LinkedIn, the membership grows by approximately two new members every second~\cite{LinkedIn}. 
Every second, there may be people joining and leaving a network, setting up or eliminating links to others. For example, the membership of LinkedIn grows by approximately two new members every second~\cite{LinkedIn}. As a result, it is imperative to maintain the discovered interesting communities (cohesive subgraphs) dynamically if possible rather than to recompute the communities from scratch each time to respond to the updating of nodes and edges of the network. In this paper, we focus on dynamically maintaining maximal trusses in evolving networks.

We first introduce other forms of cohesive subgraphs and then propose the challenge of maintaining trusses. 

The basic notion is clique~\cite{RePEc:spr:psycho:v:14:y:1949:i:2:p:95-116}. A clique is a subgraph where every node has links to other nodes in the subgraph. The definition of clique is too rigid. There are relaxed forms of cliques, such as quasi-clique~\cite{DBLP:conf/latin/AbelloRS02, DBLP:journals/tods/ZengWZK07} and n-clique~\cite{n_clique}. Quasi-clique relaxes the definition of clique by asking each node to connect to a certain percentage of other nodes. Quasi-clique can be defined based nodes~\cite{DBLP:journals/tods/ZengWZK07} and edges~\cite{DBLP:conf/latin/AbelloRS02}. $n$-clique relaxes the distance between any two nodes in a clique from 1 to $n$, i.e. two nodes can be considered as connected if they are connected by at most $n$ hops of edges. $n$-clan~\cite{n_clan} is a restricted form of $n$-clique by further imposing a constraint on the diameter. $n$-club~\cite{n_clan} removes the $n$-clique requirement from the $n$-clan, asking for only diameter constraint. $k$-plex~\cite{Seidman1978} is also a relaxed form of clique. It requires each node in a clique of $x$ nodes to have $x-k$ links to other nodes. Here, $k$ can be considered as a tolerant factor. $k$-plex is similar to quasi-clique. The difference is that quasi-clique asks for a percentage but $k$-plex asks for a number of links. The common feature of the above notions is that their computation are all NP-hard. 

Another interesting notion, recently attracting the attention of researchers, is $k$-core~\cite{Seidman1983269}. $k$-core is the largest subgraph where each node has its degree at least $k$.  $k$-core can somehow catch a cohesive graph, because in such a graph, every node has at least $k$ links to other nodes. The computation and maintenance of $k$-core is polynomial. However, $k$-core may not be very accurate because the existence of bridges. %For example, in Fig.~\ref{fig:intro_example}, it is more suitable to regard the graph as two cohesive subgraphs, though the graph itself is a $k$-core. 
This has been observed in~\cite{DBLP:conf/edbt/ZhouLYLCL12}, where the authors use maximal induced k-connected subgraphs (or $k$-strong subgraphs termed in~\cite{DBLP:journals/corr/cs-DS-0207078}) to model cohesive subgraphs. The computation of k-strong subgraphs is also expensive, though polynomial. The maintenance of k-strong subgraphs is also time-consuming~\cite{DBLP:journals/tpds/LiangBS01}. 

Considering the computation and maintenance difficulty of $k$-strong subgraphs, we are expecting a model that should be less expensive to compute and maintain, but still preserve the good property of $k$-strong subgraphs. $k$-truss fits in this category. Firstly, a $k$-truss is both a $(k-1)$-core~\cite{Wang:2012:TDM:2311906.2311909} and a $(k-1)$-connected subgraph, since a $(k-1)$-core is a $(k-1)$-connected graph. Secondly, the computation of $k$-truss is $O(m^{1.5})$, where $m$ is the number of edges. It is low polynomial. However, it is still infeasible to recompute the trusses frequently on evolving networks. To tackle this problem, we study how to maintain $k$-trusses in this paper. Our result is that maintaining $k$-truss is $O(|E_l|)$, where $E_l$ is the set of affected edges whose truss numbers need to be updated. In a large graph, we usually have $|E_l| << |E|$. This means $k$-truss may be a promising structure to model cohesive subgraphs in practice.

\begin{example}
Fig.~\ref{fig:truss1} shows the relationships of actors studied by S. Freeman and L. Freeman~\cite{DBLP:journals/web/truss}. Fig.~\ref{fig:truss1} shows the entire network. Fig.~\ref{fig:truss2} shows the maximal 4-trusses. There are two in total. As the example shows, in either 4-truss, each edge is in at least 2 triangles. Fig.~\ref{fig:truss3} shows the 3-core of the network, where each node has at least 3 neighbors. The 3-strong subgraph of the network is the same as the 3-core in this example.  
\end{example}


\begin{figure}[t]
  \centering
  \subfigure[Reciprocated Friendship and Meeting Relations]{\label{fig:truss1}
    %\includegraphics[scale=0.5]{fig/epinion30.eps}}
    \includegraphics[height=64mm,width=80mm]{truss1.eps}}
 %\hskip 0.1in
  \subfigure[4-trusses]{\label{fig:truss2}
    \includegraphics[height=45mm,width=40mm]{truss3.eps}} 
 %\hskip 0.1in
  \subfigure[3-cores]{\label{fig:truss3}
    \includegraphics[height=45mm,width=40mm]{truss2.eps}}
\caption{Examples of $k$-trusses and $k$-cores}
\label{fig:truss}
\end{figure} 
  
Finally, we summarize the main contributions of this paper as follows:
\begin{itemize}
    \item We are the first to study the truss maintenance problem.

    \item We discuss a set of important truss maintenance properties by answering the following questions ``which trusses may be affected'', ``how much effect will an update produce'', ``how far will the effect spread''. 
    
    \item We devise effective truss maintenance algorithms for edge deletions and edge insertions. We prove the correctness of the algorithms and analyze the complexity of the maintenance algorithms.
    
    \item We propose to build truss indexes to speed up the evaluation of truss queries. We also introduce how to maintain the indexes.

    \item The truss maintenance algorithms and truss index maintenance algorithms are demonstrated as efficient by the experiments.
\end{itemize}


Here is a roadmap of this paper. In Section~\ref{sect:prel}, we provide a formal definition of the problem, and introduce some necessary notations. In Section~\ref{sect:properties}, we discuss the properties of truss maintenance. In Section~\ref{sect:algorithms}, we show the algorithms of performing edge deletions or insertions. In Section~\ref{sect:index}, we show how to build and maintain truss indexes. Experiment results are shown in Section~\ref{sect:experiments}. Related works and conclusions are in Section~\ref{sect:related} and Section~\ref{sect:conclusion} respectively.







\section{Preliminaries}
\label{sect:prel}

In this work, we consider only undirected, unweighted simple graphs. The truss definition and maximal truss definition have already been introduced in Section 1. Apparently, if an edge $e$ is in a $k$-truss, it must be in a $(k-1)$-truss which is a supergraph of the $k$-truss. We define $\phi(e)$ as the maximal truss number of the trusses that edge $e$ can reside in. This truss is denoted as $T_{\phi(e)}$. We define the global support of an edge $e$ as the number of triangles containing the edge in the graph $G=(V,E)$, denoted as $sup(e,G)$. Similarly, we define the local support of an edge $e$ in a subgraph $G_s=(V_s,E_s)$ ($V_s \subseteq V$ and $E_s \subseteq E$) as the number of triangles containing $e$ in $G_s$, denoted as $sup(e,G_s)$.
%For a given $k$, $k$-truss is unique in a graph.

%$k$-truss and maximal $k$-truss are defined in the introduction. Let $\phi(e)$ denote the maximal truss number that $e$ is contained in a truss.

\begin{lemma}
Given a graph $G$, we have the following:
\[
\phi(e) \leq sup(e,T_{\phi(e)}) + 2 \leq sup(e,G) + 2
\]

\label{lemm:support}
\end{lemma}

%For an edge $e$, we have the property: the truss number of $e$ <= local support of $e$ <= global support of $e$. 

To help with the discussions, we introduce some notions. Let $a$, $b$ be two nodes, $e=(a,b)$ be an edge to be deleted or inserted between nodes $a$ and $b$, $n(a)$ and $n(b)$ be the neighbor nodes of $a$ and $b$ respectively, we define $S_{a,b} = n(a) \cap n(b)$ as the common neighbors of $a$ and $b$, define $E_{S_{a,b}\leftrightarrow \{a,b\}} = \{(n_1,n_2): n_1 \in S_{a,b}, n_2 \in \{a,b\} \}$ as the set of edges between $S_{a,b}$ and $\{a,b\}$. Furthermore, we define $k_{max}(e)$ and $k_{min}(e)$ as the maximum and minimum truss number of the edges in  $E_{S_{a,b}\leftrightarrow \{a,b\}}$, i.e. $k_{max}(e) = max\{\phi(e') : e' \in E_{S_{a,b}\leftrightarrow \{a,b\}}  \}$ and $k_{min}(e) = min\{\phi(e') : e' \in E_{S\leftrightarrow \{a,b\}} \}$. 

%Property: k-truss may not contain a k-clique

%Define support and local support. $E_{T_k}$ as $k$-truss of $G$, truss number $\phi(e)$.

%\begin{lemma}
%The local support of an edge is no less than the truss number of the edge.
%\label{lemma:localsupport}
%\end{lemma}

A notation table is given in Table~\ref{tab:notations} for easy reference. In the main part of our discussion, we consider one insertion and one deletion only, multiple insertions and deletions can be regarded as repeating single insertion and deletion.


\begin{table}[t]
\small\small \label{tab:notations} \caption{Notations and Descriptions}

\begin{center}

{\footnotesize

\begin{tabular}{l|l}

\hline
Notation &  Description\\
\hline \hline
$\phi(e)$ & the maximal truss number of the trusses\\
          & that edge $e$ resides in\\
\hline
$T_{\phi(e)}$ & the maximal $\phi(e)$-truss that \\
              & contains edge $e$ \\
\hline
$n(a)$      & the set of neighbor nodes of node $a$ \\
\hline
$S_{a,b}$ & the common neighbors of node $a$ and $b$: \\
& $n(a) \cap n(b)$ \\
\hline
$E_{S_{a,b}\leftrightarrow \{a,b\}}$ &  the set of edges between $S_{a,b}$ and $\{a,b\}$: \\ 

& $\{(n_1,n_2): n_1 \in S_{a,b}, n_2 \in \{a,b\} \}$ \\
\hline
$k_{max}(e)$ & the maximal truss number of the edges in \\
& $E_{S_{a,b}\leftrightarrow \{a,b\}}$: $max\{\phi(e') : e' \in E_{S_{a,b}\leftrightarrow \{a,b\}}  \}$ \\
\hline
$k_{min}(e)$ & the minimal truss number of the edges in \\
& $E_{S_{a,b}\leftrightarrow \{a,b\}}$: $min\{\phi(e') : e' \in E_{S_{a,b}\leftrightarrow \{a,b\}}  \}$ \\
\hline
\end{tabular}
}

\end{center}
\end{table}


%For short, we use insertion and deletion to refer edge insertion and edge deletion. 
%In the main part of our discussion, we consider one insertion and one deletion only, multiple insertions and deletions can be regarded as repeating single insertion and deletion. %In the experiment part, we will show the ``competence ratio'' of our methods.

\section{Truss Maintenance Properties}
\label{sect:properties}

In this section, we discuss some properties for truss maintenance under one insertion and one deletion. Before we proceed introducing the algorithms in Section~\ref{sect:algorithms} to tackle the truss maintenance problem, we realize it is important and helpful to discuss some theoretical findings first. This will underpin the design of the algorithms. Given a deletion or an insertion, we believe a reader is prone to ask the following questions:

\begin{enumerate}
 \item[$Q_1$] \emph{Which} trusses may be affected? -- A set of $k$-trusses with different $k$'s may be affected. What are the affected $k$'s?
 \item[$Q_2$] \emph{How much} effect will an update produce? -- It is natural to assume that one update will affect the truss numbers of the other edges by at most 1. Is this true?
 \item[$Q_3$] \emph{How far} will the effect spread? -- Will the effect be bounded within an area or can the effect spread far away?
\end{enumerate}

Before answering the questions raised above, we introduce the following observation. The correctness is obvious.  

\begin{observation}
After an insertion, the truss number of any edge will not decrease; after a deletion, the truss number of any edge will not increase.
\label{lemma:obvious}
\end{observation}

%Throughout this paper, for the sake of easy understanding, we start discussions on deletions first and then insertions. When we say ``an edge is affected'', we mean ``the truss number of an edge is affected''.

\subsection{How much effect will an update produce?}

We start with the ``\emph{how much}'' question ($Q_2$) first, because the answer is easier to understand and will be used to answer the ``\emph{which}'' question ($Q_1$). The answer to $Q_2$ is given in Lemma~\ref{lemma:how_much_effect}.
 
\begin{lemma}
After one deletion or insertion, if an edge is affected, the truss number is affected by at most 1, i.e. increased by 1 or decreased by 1.
\label{lemma:how_much_effect}
\end{lemma}

\begin{proof}
We prove the deletion first and then the insertion.

Let $e$ be an edge to be deleted and its truss number be $\phi(e)$, firstly any edge $e'$ with truss number $\phi(e')$ more than $\phi(e)$ is not affected, because $e$ is not in the $\phi(e')$-truss since $\phi(e')>\phi(e)$, therefore deleting $e$ will not affect any edge in the $\phi(e')$-truss, i.e. $e'$ is still in the $\phi(e')$-truss. Secondly, this time, let $e'$ be any edge in the $\phi(e')$-truss $T_{\phi(e')}$ with $\phi(e') \leq \phi(e)$, after deleting $e$, the global and local support of $e'$ will reduce by at most 1 respectively (both may remain unchanged), because $e$ and $e'$ only participate together in at most one triangle. As a result, after deleting $e$, $e'$ is guaranteed to be in the $(\phi(e')-1)$-truss. In both cases, the effect is not more than 1.

The insertion follows the deletion, and can be proved by contradiction. Suppose inserting $e$ increases the truss number of an edge $e'$ by more than 1, then for the updated graph, deleting $e$ will cause the truss number of $e'$ to decrease by more than 1. This contradicts the first (deletion) part of the proof.  
\end{proof}

\subsection{Which trusses may be affected?}

The answer to this ``\emph{which}'' question is given in Theorem~\ref{theo:which_affected_delete} (for deletion) and Theorem~\ref{theo:which_affected_insert} (for insertion). 

\begin{theorem}
For deletion, let $e=(a,b)$ be the to-be-deleted edge, (a) if $S_{a,b} = \emptyset$ or $k_{min}(e) > \phi(e)$, no other edges are affected; (b) if $S_{a,b} \neq \emptyset$ and $k_{min}(e) \leq \phi(e)$, the possibly affected trusses must have truss numbers within the range $[k_{min}(e), \phi(e)]$.
\label{theo:which_affected_delete}
\end{theorem}

\begin{proof} For case (a), if $S_{a,b} = \emptyset$, it is obvious that no other edges are affected, because no triangles contain $(a,b)$; if $k_{min}(e) > \phi(e)$, no other edges are affected, because any edge $e'$ with truss number $\phi(e')$ more than $\phi(e)$ is not affected. The reason is that $e=(a,b)$ is not in the $\phi(e')$-truss containing $e'$ since $\phi(e')> \phi(e)$, therefore deleting $e$ will not affect $e'$.

For case (b), $S_{a,b} \neq \emptyset$ and $k_{min}(e) \leq \phi(e)$, (1) firstly, again, as proved in case (a), any edge $e'$ with truss number $\phi(e')$ more than $\phi(e)$ is not affected. (2) next, we prove that any edge with truss number less than $k_{min}(e)$ will not be affected. Let $e'$ be an edge with truss number $\phi(e') < k_{min}(e)$, then according to Lemma~\ref{lemma:how_much_effect}, after deleting $e$, all edges in $E_{S_{a,b}\leftrightarrow \{a,b\}}$ remain in the $\phi(e')$-truss, because the truss number of an edge can be affected by at most 1 and the minimum truss number directly affected by deleting $e$ is $k_{min}(e)$. As a result, the updated $\phi(e')$-truss is the same as the old $\phi(e')$-truss but without the deleted edge $e$, and thus the edge $e'$ remains in the $\phi(e')$-truss. As a result, combining case (1) and case (2), the possibly affected trusses are in the range of $[k_{min}(e), \phi(e)]$.
\end{proof}

Moreover, we show that the range $[k_{min}(e), \phi(e)]$ is tight with an example. Let $K_n$ denote a complete graph with $n$ nodes, suppose a graph is joined by a set of complete graphs $K_{k}, K_{k-1},...,K_{t}$ $(t \geq 3)$ on an edge $e$, i.e. $e$ is the only shared edge between $K_{k}, K_{k-1},...,K_{t}$, in such a graph, all edges in the subgraph $K_k$ including $e$ have the truss number $k = \phi(e)$, all edges in the subgraph $K_{k-1}$ except $e$ have the truss number $k-1$, ..., all edges in the subgraph $K_t$ except $e$ have the truss number $t$. Apparently, in this example, $k_{min}(e)=t$. If we delete the edge $e$, we can find that the truss numbers of all other edges will decrease by 1. These edges originally have the truss numbers ranging from $t=k_{min}(e)$ to $k=\phi(e)$, therefore the range $[k_{min}(e), \phi(e)]$ is tight. Fig.~\ref{fig:tightness} is one such example. A $K_3$, a $K_4$ and a $K_5$ are joined at edge $(a,b)$. If we delete $(a,b)$, all the other edges are affected and they originally have the truss range $[3,5]$. Here, for the edge $(a,b)$, $k_{min}((a,b))=3$ and $\phi((a,b))=5$. The affected range $[3,5]$ is tight in this example.


\begin{figure}[t]
    \centering
    {\includegraphics[width=60mm]{tightness.eps}}
    \caption{A $K_3$, a $K_4$ and a $K_5$ are joined at $(a,b)$}
    \label{fig:tightness}
\end{figure}



Before presenting Theorem~\ref{theo:which_affected_insert} for the insertion, we introduce Lemma~\ref{lemma:together} and Lemma~\ref{lemma:truss_bound} first to support the proof of Theorem~\ref{theo:which_affected_insert}. 

%To help with the discussion, we introduce some notions first. Let $a$, $b$ be two nodes, $e=(a,b)$ be an edge to be deleted or inserted between nodes $a$ and $b$, $nb(a)$ and $nb(b)$ be the neighbor nodes of $a$ and $b$ respectively, let $S = nb(a) \cap nb(b)$ be the common neighbors of $a$ and $b$, let $E_{S\leftrightarrow \{a,b\}} = \{(n_1,n_2): n_1 \in S, n_2 \in \{a,b\} \}$ be the set of edges between $S$ and $\{a,b\}$, let $k_{max}$ and $k_{min}$ be the maximum and minimum truss number of the edges in  $E_{S\leftrightarrow \{a,b\}}$, i.e. $k_{max} = max\{\phi(e) : e \in E_{S\leftrightarrow \{a,b\}}  \}$ and $k_{min} = min\{\phi(e) : e \in E_{S\leftrightarrow \{a,b\}} \}$. We have the main result as Theorem~\ref{theo:which_affected_delete} and~\ref{theo:which_affected_insert}. %A EXAMPLE HERE TO EXPLAIN THE NOTIONS.
%Before introducing Theorem~\ref{theo:which_affected_delete} and~\ref{theo:which_affected_insert}, we give Lemma~\ref{lemma:together} and~\ref{lemma:truss_bound} first in order to support the proof of the theorem. 

\begin{lemma}
After inserting an edge $e$, if the truss number of an edge $e'$ increases from $\phi(e')$ to $\phi(e')+1$, then the inserted edge $e$ must be in the $(\phi(e')+1)$-truss containing $e'$ in the updated graph.
\label{lemma:together}
\end{lemma}

\begin{proof}
By contradiction, if the inserted edge $e$ is not in the $(\phi(e')+1)$-truss containing $e'$ in the updated graph, then deleting $e$ will not reduce the truss number of $e'$. This contradicts with the assumption that after inserting $e$, the truss number of $e'$ increases from $\phi(e')$ to $\phi(e')+1$.
\end{proof}


%\begin{lemma}
%In a k-truss subgraph, there must be a node with local triangles $(k-2)$, otherwise the $k$-truss will be $(k+1)$-truss according to definition.
%\end{lemma}


\begin{lemma}
For any edge $e=(a,b)$ in a graph, we have the following: %$k \leq max\{\phi(e): e \in E_{S\leftrightarrow \{a,b\}}  \} $. %We can let the property hold for $k=2$ by defining the highest truss number as 2 when $S=\emptyset$.
\[
%\begin{equation}
 \left\{ {\begin{array}{*{20}c}
   {\phi(e) =2 } & {(E_{S_{a,b}\leftrightarrow \{a,b\}} = \emptyset)}  \\
   {\phi(e) \leq max\{\phi(e'): e' \in E_{S_{a,b}\leftrightarrow \{a,b\}}  \} } & {(E_{S_{a,b}\leftrightarrow \{a,b\}} \neq \emptyset)}  \\
\end{array}} \right.
\]
%\label{eq:truss_bound}
%\end{equation}
\label{lemma:truss_bound}
\end{lemma}

\begin{proof} If $E_{S_{a,b}\leftrightarrow \{a,b\}} = \emptyset$ (i.e. $S_{a,b}=n(a) \cap n(b)=\emptyset$), the truss number of $(a,b)$ is 2. The lemma holds naturally. If $E_{S_{a,b}\leftrightarrow \{a,b\}} \neq \emptyset$, assume $\phi(e) > max\{\phi(e'): e' \in E_{S_{a,b}\leftrightarrow \{a,b\}}  \} $, then we have that edge $(a,b)$ is in a $\phi(e)$-truss and all the edges in $E_{S_{a,b}\leftrightarrow \{a,b\}}$ are not in the $\phi(e)$-truss. Therefore, edge $(a,b)$ does not have supporting triangles in the $\phi(e)$-truss, so $\phi(e)$ must be 2. This contradicts with the assumption $\phi(e) > max\{\phi(e'): e' \in E_{S_{a,b}\leftrightarrow \{a,b\}}  \} $ in which it is apparent that $max\{\phi(e'): e' \in E_{S_{a,b}\leftrightarrow \{a,b\}}  \} \geq 3$ if $E_{S_{a,b}\leftrightarrow \{a,b\}} \neq \emptyset$, so $\phi(e) \leq max\{\phi(e'): e' \in E_{S_{a,b}\leftrightarrow \{a,b\}}  \} $ when $E_{S_{a,b}\leftrightarrow \{a,b\}} \neq \emptyset$. 
\end{proof}

Lemma~\ref{lemma:truss_bound} says the maximum truss number of edges in $E_{S_{a,b}\leftrightarrow \{a,b\}}$ is an upper bound of the truss number of $(a,b)$. Similarly, readers may wonder ``do we have the minimum truss number of the edges in $E_{S_{a,b}\leftrightarrow \{a,b\}}$ as a lower bound of the truss number of $(a,b)$ when $E_{S_{a,b}\leftrightarrow \{a,b\}} \neq \emptyset$?'', i.e. ``do we have $\phi(e) \geq min\{\phi(e'): e' \in E_{S_{a,b}\leftrightarrow \{a,b\}}  \} $ when $E_{S_{a,b}\leftrightarrow \{a,b\}} \neq \emptyset$?'' The answer is no. We illustrate this through an example in Fig.~\ref{fig:counter_example}, where $\phi((a,b))=3$, $S_{a,b}=n(a)\cap n(b)=\{c\}$, $E_{S_{a,b}\leftrightarrow \{a,b\}} = \{(a,c),(b,c)\}$, $min\{\phi(e'): e' \in E_{S_{a,b}\leftrightarrow \{a,b\}}  \}$ = $min\{\phi((a,c))=4,\phi((b,c))=4 \} = 4$. In this example, $\phi((a,b)) < min\{\phi(e'): e' \in E_{S_{a,b}\leftrightarrow \{a,b\}}  \}$.

\begin{figure}[t]
    \centering
    {\includegraphics[width=60mm]{counter_example.eps}}
    \caption{An example showing $\phi((a,b)) \geq min\{\phi(e'): e' \in E_{S_{a,b}\leftrightarrow \{a,b\}}  \} $ does not hold. }
    \label{fig:counter_example}
\end{figure}


%The lemma can be proved using an example. Let (a,b) be an edge between two k-trusses (k >= 3), then the truss number of (a,b) is 2, but (a,b) neighbour edges all have truss number 3. 

Now we are ready to state the following theorem. 
%introduce and prove Theorem~\ref{theo:which_affected_insert}.


\begin{theorem}
For insertion, let $e=(a,b)$ be the newly inserted edge, (a) if $S_{a,b} = \emptyset$ or $k_{min}(e) > |S_{a,b}|+1$, no other edges are affected; (b) if $S_{a,b} \neq \emptyset$ and $k_{min}(e) \leq |S_{a,b}|+1$, the possibly affected trusses must have truss numbers within the range $[k_{min}(e), min(|S_{a,b}|+1, k_{max}(e))]$.
%\[
%\begin{equation}
% \left\{ {\begin{array}{*{20}c}
%   {[k_{min}(e), min(|S_{a,b}|+1, k_{max}(e))]} & {( k_{min}(e) \leq |S_{a,b}|+1 )}  \\
%   { \emptyset } & {(k_{min}(e) > |S_{a,b}|+1)}  \\
%\end{array}} \right.
%\]
\label{theo:which_affected_insert}
\end{theorem}

\begin{proof} For case (a), if $S_{a,b} = \emptyset$, obviously no other edges are affected; if $k_{min}(e) > |S_{a,b}|+1$, no other edges are affected because any edge $e'$ with $\phi(e') > |S_{a,b}|+1$ is not affected. Assume the truss of $e'$ is affected and increased to $\phi(e')+1$, according to Lemma~\ref{lemma:together}, $(a,b)$ will be in the $(\phi(e')+1)-truss$ with the truss number larger than $|S_{a,b}|+2$. However, it is obvious that $|S_{a,b}|$ is the global support of $(a,b)$, so $|S_{a,b}|+2$ is an upper bound of $(a,b)$'s truss number. A contradiction appears.  

For case (b), $S_{a,b} \neq \emptyset$ and $k_{min}(e) \leq |S_{a,b}|+1$, if an edge $e'$ is affected, then we must have (1) $\phi(e') \leq |S_{a,b}|+1$, (2) $\phi(e') \leq k_{max}(e)$ and (3) $\phi(e') \geq k_{min}(e)$. We now prove each part respectively. (1) Firstly, $\phi(e') \leq |S_{a,b}|+1$ is proved in case (a). (2) Secondly, any edge $e'$ with $\phi(e') > k_{max}(e)$ is not affected. We prove by contradiction. Assume the truss number of $e'$ is increased to $\phi(e')+1$, according to Lemma~\ref{lemma:together}, the truss number of the inserted edge $e=(a,b)$, $\phi(e)$, is at least $\phi(e')+1$ in the updated graph, so we have $\phi(e) > k_{max}(e) + 1$. On the other hand, according to Lemma~\ref{lemma:how_much_effect}, in the updated graph, $max\{\phi(e') : e' \in E_{S_{a,b}\leftrightarrow \{a,b\}}  \} \leq k_{max}(e) + 1$. Furthermore, according to Lemma~\ref{lemma:truss_bound}, in the updated graph, $\phi(e) \leq max\{\phi(e') : e' \in E_{S_{a,b}\leftrightarrow \{a,b\}}  \} \leq k_{max}(e) + 1$. There is a contradiction. (3) Finally, any edge $e'$ with $\phi(e') < k_{min}(e)$ is not affected. Since $\phi(e') < k_{min}(e)$, all the edges in $E_{S_{a,b}\leftrightarrow \{a,b\}}$ are in a $(\phi(e')+1)$-truss. As a result, there is no new edges adding into the $(\phi(e')+1)$-truss except the newly inserted one, because all the directly affected edges $E_{S_{a,b}\leftrightarrow \{a,b\}}$ are all already in the $(\phi(e')+1)$-truss. The unchangingness of any $(\phi(e')+1)$-truss with $\phi(e')<k_{min}(e)$, together with Observation~\ref{lemma:obvious}, implies that current $\phi(e')$-truss edges remain as $\phi(e')$-truss edges. 
\end{proof}

Then, let us inspect the tightness of $[k_{min}(e), min\{|S_{a,b}|+1, k_{max}(e)\}]$. Similar to the deletion, suppose a graph is joined by a set of complete graphs $K_{k}, K_{k-1},...,K_{t} (t \geq 3)$ on an edge $e$, but now $e$ was deleted, and we want to insert $e$ back into the $e$-deleted graph. Then the affected trusses will have truss ranges from $t-1$ to $k-1$. $t-1$ and $k-1$ are the $k_{min}(e)$ and $k_{max}(e)$ of the to-be-inserted edge $e$ in the $e$-deleted graph. Sometimes, $k_{max}(e)$ may be larger than $|S_{a,b}|+1$. In such cases, $[k_{min}(e),|S_{a,b}|+1]$ is the affected truss range. See Fig.~\ref{fig:k_max_large} for an example, $(a,b)$ is the edge to be inserted, $k_{max}((a,b))$ is 4 on the edge $(b,c)$, $k_{min}((a,b))$ is 3 on the edges $(a,d)$, $(b,d)$ and $(a,c)$, $S_{a,b}=\{c,d\}$, so $k_{min}((a,b)) = |S_{a,b}|+1 = 3 < k_{max}((a,b))$. The affected truss range is $[k_{min}((a,b)), |S_{a,b}|+1]$, which is $[3,3]$. In this example, the affected edges are $(a,d)$, $(b,d)$, $(a,c)$ and $(c,d)$. All of them originally have truss number 3. In the next example, $k_{min}((a,b)) > |S_{a,b}|+1$, see Fig.~\ref{fig:k_min_large}. Again, $(a,b)$ is the to-be-inserted edge, $S_{a,b}=\{c\}$, $k_{max}((a,b))=4$ on the edge $(b,c)$, $k_{min}((a,b))=3$ on the edge $(a,c)$, $|S_{a,b}|+1 = 2 < k_{min}((a,b))$. No existing edges are affected when we insert $(a,b)$. 

    


\begin{figure}[t]
    \centering
    {\includegraphics[width=60mm]{k_max_large.eps}}
    \caption{$k_{max}((a,b))=4$, $k_{min}((a,b))=3$, $S_{a,b}=\{c,d\}$, $k_{min}((a,b)) \leq |S_{a,b}|+1<k_{max}((a,b))$, so the affected truss range is $[k_{min}((a,b)), |S_{a,b}|+1]$.}
    \label{fig:k_max_large}
\end{figure}

\begin{figure}[t]
    \centering
    {\includegraphics[width=60mm]{k_min_large.eps}}
    \caption{$k_{max}((a,b))=4$, $k_{min}((a,b))=3$, $S_{a,b}=\{c\}$, $k_{min}((a,b)) > |S_{a,b}|+1$, so no other edges are affected.}
    \label{fig:k_min_large}
\end{figure}


Theorem~\ref{theo:which_affected_delete} and~\ref{theo:which_affected_insert} tell us that, for an update, we do not need to inspect all the edges in the graph, instead we only need to inspect a subset of edges whose truss numbers are within a certain range. 


\subsection{How far will the effect spread?}
\label{sect:how_far}

From the above discussions, we find that the truss number of an edge is affected because the local support of the edge is changed. When we delete or insert an edge $(a,b)$, recall that $S=n(a) \cap n(b)$, the set of edges that are directly affected is $E_{S_{a,b}\leftrightarrow \{a,b\}}$, because $(a,b)$ forms triangles with the edges in $E_{S_{a,b}\leftrightarrow \{a,b\}}$. As a result, the global support of the edges in $E_{S_{a,b}\leftrightarrow \{a,b\}}$ will change, and this may lead to changes of their local support, eventually the truss numbers of these edges may change. Furthermore, the effect may spread to the neighbor edges of the edges in $E_{S_{a,b}\leftrightarrow \{a,b\}}$. In this section, we will discuss how far the effect will spread. For simplicity, we only discuss deletion in all the examples in this section. The effect of insertion is similar. (one can simply insert the deleted edge back and see the impact of an insertion in the following examples.)

Firstly, we show that the effect may spread indeed. It is natural to recognize that the truss numbers of edges in $E_{S_{a,b}\leftrightarrow \{a,b\}}$ may be affected, but could other edges be affected, such as the edges incident on node $a$ or $b$ but not in $E_{S_{a,b}\leftrightarrow \{a,b\}}$? The answer is yes. We give an example in Fig.~\ref{fig:how_far_one_step}. The graph is a 4-truss. Every edge is in two triangles. If we delete $(a,b)$, directly we will have $(a,c)$, $(a,d)$, $(b,c)$, $(b,d)$ having global support 1, and thus these four edges cannot be in a 4-truss. Further, we find that there is no 4-truss in the updated graph. The truss numbers of all the other edges are reduced from 4 to 3, such as $(a,e)$, $(b,f)$, though they do not belong to $E_{S_{a,b}\leftrightarrow \{a,b\}}$. 

\begin{figure}[t]
    \centering
    {\includegraphics[width=48mm]{how_far_one_step.eps}}
    \caption{The effect may spread}
    \label{fig:how_far_one_step}
\end{figure}

Next, we give another example to show that the effect can be spread a long way away (summarized as Lemma~\ref{lemm:unlimited}). In Fig.~\ref{fig:how_far_unlimited}, there is an unlimited graph piling by the unit shown in the bottom right corner. In such a graph, every edge is in two triangles and every edge has truss number 4. If we delete edge $(a,b)$, the first set of edges whose truss numbers are affected is $(a,p_2)$, $(b,p_2)$, $(a,q_3)$, $(b,q_3)$. Each of these four edges will have only one supporting triangle, so they will no longer be in the 4-truss. Then, the effect will spread towards four directions leading to the truss number of every edge decreased by 1. 

\begin{lemma}
There is no guarantee that the update effect will end after spreading a fixed number of steps.  
\label{lemm:unlimited}
\end{lemma}

\begin{figure}[t]
    \centering
    {\includegraphics[width=63mm]{how_far_unlimited.eps}}
    \caption{The effect may spread very far}
    \label{fig:how_far_unlimited}
\end{figure}



\section{Algorithms}
\label{sect:algorithms}

Based on the properties discussed in Section~\ref{sect:properties}, we design maintenance algorithms for deleting an edge and inserting an edge.

\iffalse

\subsection{Naive method}

Base on the above properties, we can design a naive method:

The idea of the naive method is that (1) find a subgraph containing a large set of edges whose truss number may be affected; (2) then run the existing truss decomposition algorithm on the subgraph to obtain new truss numbers.

Given an insertion, suppose insert (a,b), let nb(a) intersection nb(b) = S, let nb(a)=$\{a1,...,am\}$, nb(b)=$\{b1,...,bn\}$:

1. If $|S| + 2$ <= least truss number among $\{(a,a1),..,(a,am)\}$ and $\{(b,b1),...,(b,bn)\}$, then (a,b) $\in$ $|S|$-truss, other edges are not affected. 

2. If $|S| + 2$ > least truss number among $\{(a,a1),...,(a,am)\}$ and $\{(b,b1),..,(b,bn)\}$, let the least truss number be $k_min$, find a subgraph by DFS (depth-first-search) the condition is that if an edge has truss equal or more than $k_min$, then the edge will be included in the subgraph. Do truss decomposition on the subgraph.

Given a deletion, suppose delete (a,b), let nb(a) intersection nb(b) = S, let nb(a)=$\{a1,...,am\}$, nb(b)=$\{b1,...,bn\}$, let (a,b) in k-truss in the original graph:

1. If $k <$ least truss number among $\{(a,a1),...,(a,am)\}$ and $\{(b,b1),...,(b,bn)\}$, other edges are not affected.

2. If $k >=$ least truss number among $\{(a,a1),...,(a,an)\}$ and $\{(b,b1),...,(b,bn)\}$, firstly those edges with truss number more than $k$ will not be affected, then find a subgraph by DFS (depth-first-search) the condition is that if an edge has truss equal or less than $k$, then the edge will be included in the subgraph. Do truss decomposition on the subgraph.


Property: let the truss number of (a,b) be $k (k>2)$, then $k <=$ highest truss number among $\{(a,a1),...,(a,am)\}$ and $\{(b,b1),...,(b,bn)\}$. We can let the property hold for $k=2$ by defining the highest truss number as 2 when $S=\empty$.

Conjecture: Is $k >=$ lowest truss number of edges among $\{(a,a1),...,(a,am)\}$ and $\{(b,b1),...,(b,bn)\}$? No, the example is that (a,b) is a bridge.

Another conclusion: $k <= |S|$  (the number of global triangles is a high bound of $k$)

\fi

\subsection{Deleting an edge}
\label{subsect:delete}


Inspired by the answers to the questions ``\emph{which trusses may be affected}'' and ``\emph{how far will the effect spread}'' in Section~\ref{sect:properties}, we can devise an outward inspection based truss maintenance approach for edge deletion. Firstly, we start from the to-be-deleted edge $(a,b)$ and check which neighbor edges will be directly affected if we delete $(a,b)$. These directly affected edges must be in the edge set $E_{S_{a,b}\leftrightarrow \{a,b\}}$, because other edges (the edges not in $E_{S_{a,b}\leftrightarrow \{a,b\}}$) do not participate in triangles together with $(a,b)$, and thus they are definitely not affected at the moment, although we may find that they are affected at a later time. After inspecting the set $E_{S_{a,b}\leftrightarrow \{a,b\}}$, we may find some edges in $E_{S_{a,b}\leftrightarrow \{a,b\}}$ are affected while the others are not. Then, we continue inspecting the neighbor edges of the affected edges in $E_{S_{a,b}\leftrightarrow \{a,b\}}$ and repeat the process until no newly affected edges are found. During the process, only the edges with truss numbers in the range $[k_{min}((a,b)), \phi((a,b))]$ need to be examined. This is guaranteed by Theorem~\ref{theo:which_affected_delete}. Algorithm~\ref{algo:out_delete} gives the maintenance steps. 


%To accelerate the process, we can record the local support of each edge. The local support are different for different trusses. The naive way is to record all the local support for different trusses. (may not be necessary). 

\begin{algorithm}[t]
%\SetLine
\caption{ An outwards inspection based truss maintenance algorithm for edge deletion}
\label{algo:out_delete}
{ 
\textbf{Input:} a graph $G=(V,E)$ with truss numbers associated with its edges, a to-be-deleted edge $(a,b)$; \\
\textbf{Output:} $G=(V,E$-$\{(a,b)\})$ with updated truss numbers associated with its edges;  
  \begin{algorithmic}[1]
  					\STATE delete the edge $(a,b)$;
            \STATE put the edges in $E_{S_{a,b}\leftrightarrow \{a,b\}}$ with truss numbers in $[k_{min}((a,b)), \phi((a,b))]$ (Theorem~\ref{theo:which_affected_delete}) into a queue;
                        \WHILE{the queue is not empty}
                        				\STATE take an edge $(v_1,v_2)$ from the queue;
                        				\IF{ $(v_1,v_2)$ is not marked $\wedge$ $localSupport((v_1,v_2), \phi((v_1,v_2))) < \phi((v_1,v_2))-2$ }\label{line:decrease}
                        							\STATE decrease the truss number of $(v_1, v_2)$;
                        							\STATE mark the edge $(v_1,v_2)$;
                        							\STATE put the edges in $E_{S_{v_1,v_2}\leftrightarrow \{v_1,v_2\}}$ with truss numbers in $[k_{min}((a,b)), \phi((a,b))]$ (Theorem~\ref{theo:which_affected_delete}) into the queue;
                        								
                        				\ENDIF
                        				
                        \ENDWHILE
                        \STATE start from the edge $(a,b)$, do a depth-first or breadth-first search to unmark all the marked edges; \\
                        \COMMENT {This is to guarantee the correctness of processing the next deletion or insertion.}
                        
             \RETURN $G$;
   \end{algorithmic}
}%\caption{ $decrease(G,(v_1,v_2))$}
{
\textbf{Step~\ref{line:decrease}:} $localSupport((v_1,v_2), k)$ \\ 
\textbf{Input:} an edge $(v_1,v_2)$ and a truss number $k$;\\
\textbf{Output:} the local support of the edge $(v_1,v_2)$ with respect to the truss number $k$;
  \begin{algorithmic}[1]
            \STATE $lSupport \leftarrow 0$;
            \FOR{ each node $v \in n(v_1)\cap n(v_2)$}\label{line:decreaseInter}
            		\IF{ $\phi((v,v_1)) \geq k \wedge \phi((v,v_2)) \geq k$ }
            				\STATE $lSupport \leftarrow lSupport + 1$;
            		\ENDIF
            \ENDFOR
            \RETURN $lSupport$;
   \end{algorithmic}
}

\end{algorithm}


%count how many triangle containing the edge also has the other two edges no less than $k$, this number is the local support; //compute local support;

We now explain Algorithm~\ref{algo:out_delete} in detail. Line 1 deletes the edge $(a,b)$. Line 2 puts the pruned edge set $E_{S_{a,b}\leftrightarrow \{a,b\}}$ into a queue, since this is the set of edges whose truss numbers may be directly affected by deleting $(a,b)$. While the queue is not empty (line 3), i.e. there are still some edges that may be affected directly or indirectly waiting to be inspected, we take an edge from the queue (line 4), and check whether the truss number of the edge should be decreased (line 5). The first condition ``$(v_1,v_2)$ is not marked'' means if the truss number of an edge has been decreased before (see line 7) we do not need to decrease the truss number again, because according to Lemma~\ref{lemma:how_much_effect} we only need to decrease the truss number once. The second condition of line 5 checks whether the edge $(v_1,v_2)$ has enough local support with respect to the truss number $\phi((v_1,v_2))$. If not, i.e. ``$localSupport((v_1,v_2), \phi((v_1,v_2))) < \phi((v_1,v_2))-2$'' is $true$, we decrease the truss number of $(v_1,v_2)$ (line 6), mark the edge $(v_1,v_2)$ (line 7) and put the pruned edges in $E_{S_{v_1,v_2}\leftrightarrow \{v_1,v_2\}}$ with truss numbers in $[k_{min}((a,b)), \phi((a,b))]$ 
into the queue (line 8). The truss numbers of the edges in the set $E_{S_{v_1,v_2}\leftrightarrow \{v_1,v_2\}}$ may be affected because the truss number of the edge $(v_1,v_2)$ is affected. On the contrary, if the condition ``$localSupport((v_1,v_2), \phi((v_1,v_2))) < \phi((v_1,v_2))-2$'' is $false$, no action is required. We simply go on to inspect the next edge in the queue, i.e. start a new loop in the while clause from line 4. Finally, after we empty the queue, the truss numbers of the edges in $G$ have been updated. Line 11 is a post-processing step that prepares for the next update operation.

We now explain the function $localSupport((v_1,v_2), k)$. In order to compute the local support of the edge $(v_1,v_2)$ with respect to the truss number $k$, we need to count how many triangles containing the edge $(v_1,v_2)$ also have the other two edges with truss numbers no less than $k$. This equals to count how many such node $v \in S_{v_1,v_2} = n(v_1)\cap n(v_2)$ having both $\phi((v,v_1))$ and $\phi((v,v_2))$ no less than $k$. 

%To check whether the truss number of an edge $(v_1,v_2)$ needs to be decreased, the idea is to compare the local support of the edge with the current truss number of the edge $k$. If the local support is less than the truss number $k$ minus 2 (line 8), we know the edge $(v_1,v_2)$ cannot be in a $k$-truss according to Lemma~\ref{lemma:localsupport}, so $true$ will be returned (line 9), otherwise $false$ is returned (line 11). 

In the following, we will prove Algorithm~\ref{algo:out_delete} is correct and analyze the algorithm complexity. 

\begin{lemma}
Algorithm~\ref{algo:out_delete} is correct. The complexity is $O(|E_l|)$, where $|E_l|$ is the number of edges whose local support are affected and $|E_l| << |E|$. 
\end{lemma}

\begin{proof}
The first possibly affected set of edges are put into the queue in line 2. The following possibly affected edges are put into the queue in line 8. All possibly affected edges are put into the queue by Algorithm~\ref{algo:out_delete}. When an edge $(v_1,v_2)$ is taken from the queue to be inspected, the source affected edge which leads $(v_1,v_2)$ to be put into the queue has been updated (the truss number is decreased). This guarantees the current computed local support of $(v_1,v_2)$ is an upper bound of the local support in the final updated graph. Therefore, it is safe to decrease the truss number of $(v_1,v_2)$ if the current local support is already less than $\phi((v_1,v_2))-2$. It is also guaranteed that the truss number can be decreased only once.


Complexity of Algorithm~\ref{algo:out_delete}: Assume the graph $G=(V,E)$ is stored in an adjacency list, we analyze the neighbor set intersection $n(a) \cap n(b)$ first. By using a hash table, $n(a) \cap n(b)$ can be done in $O(|n(a)|+|n(b)|)$ time. This is accomplished by firstly putting the edges in $n(a)$ into the hash table, and then hash-check the edges in $n(b)$. (An inferior method using nested-loop checks requires $O(|n(a)||n(b)|)$ time.) Back to our discussion on Algorithm~\ref{algo:out_delete}, line 1, line 2 and line 11 have complexity $O(1)$, $O(|n(a)|+|n(b)|)$ and $O(|E|)$ respectively. These are dominated by the while clause, line 3 to line 10. In the while clause, the critical step is line 5 and line 8. For line 5, the function $localSupport()$ has complexity $O(|n(v_1)|+|n(v_2)|)$, because line~\ref{line:decreaseInter} in the function $localSupport()$ has the complexity $O(|n(v_1)|+|n(v_2)|)$ and all the other steps in the function $localSupport()$ have the complexity $O(1)$. For line 8, the complexity is $O(|n(v_1)|+|n(v_2)|)$ as well. As a result, the complexity of Algorithm~\ref{algo:out_delete} is $O(n_q \cdot deg_{max})$, where $n_q$ is the number of edges ever put into the queue and $deg_{max}$ is the maximum degree of the nodes in the graph. To analyze the bounds: in a massive graph, $deg_{max}$ can be considered as a constant. We also have $n_q  = O(|E_{l}|)$, where $|E_{l}|$ is the number of edges whose local support is affected. The reason is that an edge $(a,b)$ will be put into the queue at most $2|S_{a,b}|$ times and $2|S_{a,b}| < 2|deg_{max}|$, so $n_q < 2|deg_{max}||E_{l}|$. As a result, we have $n_q = O(|E_l|)$. As the affected edges are far less than the number of edges in the graph ($|E_l| << |E|$), the maintenance algorithm is very efficient. The cost of the maintenance algorithm is linear to the number of affected edges, which is $O(E_l)$.


\end{proof} 
%$deg_{max} \leq |V|-1$. We also have $n_q < 2|V||E|$ because an edge $(a,b)$ will be put into the queue at most $2|S_{a,b}|$ times and $2|S_{a,b}| < 2|deg_{max}| < 2|V|$.   
%In the worst case, $n_q = 2(|E|-1)$ and $deg_{max} = |V|-1$, which means every edge will be put into the queue and every edge is connected with all the other edges. For example, this is the case when we delete an edge from a complete graph. 
%The complexity of Algorithm~\ref{algo:out_delete} is then $O(|E||V|^2)$. In general, $n_q$ and $deg_{max}$ are of moderate sizes, so the maintenance algorithm is efficient. 


\subsection{Inserting an edge}
\label{subsect:insert}

When an edge is inserted, the truss maintenance includes two parts. Firstly, according to Observation~\ref{lemma:obvious} and Lemma~\ref{lemma:how_much_effect}, for some existing edges, the truss numbers should be increased by 1, and all the other existing edges keep their truss numbers unchanged. 
%Therefor, we need to find the affected edges. 
Secondly, for the newly inserted edge, the truss number needs to be determined.

\subsubsection{Different from deleting an edge}

%One may think to design an approach for inserting an edge similar to the approach designed for deleting an edge, see Algorithm~\ref{algo:out_insert_false}. The idea of the hypothesized algorithm is as follows: we start from the to-be-inserted edge (line 1). Firstly, we find which neighbor edges will have their global support increased by 1 and put them into a queue (line 2). Let $(v_1,v_2)$ be one of the edges in the queue and let its truss number be $\phi((v_1,v_2))$, we then check whether the local support of $(v_1,v_2)$ with respect to the truss number $\phi((v_1,v_2))+1$ is no less than $\phi((v_1,v_2))-1$. If so, it means that $(v_1,v_2)$ has local support at least $\phi((v_1,v_2))-1$. We then increase the truss number of $(v_1,v_2)$ by 1 and go on to inspect the neighbor edges in $E_{S_{v_1,v_2}\leftrightarrow \{v_1,v_2\}}$.

One may think to design an approach for inserting an edge similar to the approach designed for deleting an edge. The idea of the hypothesized algorithm is as follows: we start from the to-be-inserted edge. Firstly, we find which neighbor edges will have their global support increased by 1 and put them into a queue. Let $(v_1,v_2)$ be one of the edges in the queue and let its truss number be $\phi((v_1,v_2))$, we then check whether the local support of $(v_1,v_2)$ with respect to the truss number $\phi((v_1,v_2))+1$ is no less than $\phi((v_1,v_2))-1$. If so, it means that $(v_1,v_2)$ has local support at least $\phi((v_1,v_2))-1$. We then increase the truss number of $(v_1,v_2)$ by 1 and go on to inspect the neighbor edges in $E_{S_{v_1,v_2}\leftrightarrow \{v_1,v_2\}}$.

The hypothesized algorithm has a similar paradigm as the deletion counterpart. However, it is not correct. The problem is that, we may miss to update some edges. In other words, after an insertion, some edges may have truss numbers increased from $k$ to $(k+1)$, but we cannot find them using the algorithm. It is safe to increase the truss number of an edge $(v_1,v_2)$ if the local support of the edge in the current $(\phi((v_1,v_2))+1)$-truss is already no less than $\phi((v_1,v_2))-1$, however, when we check the condition ``$localSupport((v_1,v_2),\phi(v_1,v_2)+1) \geq \phi((v_1,v_2))-1 $'', some edges which should finally be put into the $(\phi((v_1,v_2))+1)$-truss have not been found, so at this time, the local support may be underestimated, as a result, we may miss to update some $(\phi((v_1,v_2))+1)$-truss edges. %Let us see Fig.~\ref{} for an example.
In the following section, we introduce the correct approaches to update truss numbers in case of edge insertions.

\iffalse
\begin{algorithm}[t]
%\SetLine
\caption{ An outwards inspection based truss maintenance algorithm for edge insertion}
\label{algo:out_insert_false}
{ 
\textbf{Input:} a graph $G=(V,E)$ with truss numbers associated with its edges, a to-be-inserted edge $(a,b)$ \\
\textbf{Output:} $G=(V,E \cup \{(a,b)\})$ with updated truss numbers associated with its edges 
  \begin{algorithmic}[1]
  					\STATE insert the edge $(a,b)$;
            \STATE put the edges in $E_{S_{a,b}\leftrightarrow \{a,b\}}$ confined by Theorem~\ref{theo:which_affected_insert} into a queue;
                        \WHILE{the queue is not empty}
                        				\STATE take an edge $(v_1,v_2)$ from the queue;
                        				\IF{ $(v_1,v_2)$ is not marked $\wedge$ $localSupport((v_1,v_2),\phi(v_1,v_2)+1) \geq \phi((v_1,v_2))-1 $ }\label{line:increaseP}
                        							\STATE increase the truss number of $(v_1, v_2)$;
                        							\STATE mark the edge $(v_1,v_2)$;
                        							\STATE put the edges in $E_{S_{v_1,v_2}\leftrightarrow \{v_1,v_2\}}$ confined by Theorem~\ref{theo:which_affected_insert} into the queue;
                        								
                        				\ENDIF
                        				
                        \ENDWHILE
             \STATE compute the truss number of the inserted edge $(a,b)$;
             \STATE start from the edge $(a,b)$, do a depth-first or breadth-first search to unmark all the marked edges;
                        
             \RETURN $G$;
   \end{algorithmic}
}

\end{algorithm}
\fi





\subsubsection{Algorithm}


For truss maintenance under insertion, an intuitive, naive but correct approach is: starting from the inserted edge $e=(a,b)$, do a depth-first or breadth-first search to find the $k_{min}(e)$-truss. During the process, eliminate the edges with truss numbers more than $min(|S_{a,b}|+1,k_{max}(e))$. As a result, we can obtain a pruned $k_{min}(e)$-truss. In the end, we add the edge $e$ into the pruned $k_{min}(e)$-truss and do a truss decomposition. The truss numbers of all the edges will then be up-to-date. The correctness of this naive method is obvious, guaranteed by Theorem~\ref{theo:which_affected_insert}. However, the drawback of the naive approach is that it ignores the effect actually started from the inserted edge. In an extreme case, if we discover that the first possibly affected set of edges $E_{S_{a,b}\leftrightarrow \{a,b\}}$ are actually not affected after inserting edge $e$, we can stop the maintenance process right away, because no other edges will be affected. We only need to determine the truss number for the newly inserted edge $e$. Along this line, we design a mark-and-verify approach for truss maintenance under an edge insertion. 



\begin{algorithm}[t]
%\SetLine
\caption{ A mark-and-verify truss maintenance algorithm for edge insertion}
\label{algo:out_insert}
{ 
\textbf{Input:} a graph $G=(V,E)$ with truss numbers associated with its edges, a to-be-inserted edge $(a,b)$ \\
 \textbf{Output:} $G=(V,E \cup \{(a,b)\})$ with updated truss numbers associated with its edges 
  \begin{algorithmic}[1]
  					\STATE insert edge $(a,b)$;
            \STATE put the edges in $E_{S_{a,b}\leftrightarrow \{a,b\}}$ confined by Theorem~\ref{theo:which_affected_insert} into a queue;
                        \WHILE{the queue is not empty}
                        				\STATE take an edge $(v_1,v_2)$ from the queue;
                        				\IF{ $localSupport2((v_1,v_2),\phi(v_1,v_2)) \geq \phi((v_1,v_2))-1 $ }\label{line:increaseS}
                        							\IF{ $(v_1,v_2)$ is not marked }
                        									\STATE mark the edge $(v_1,v_2)$;
                        									\STATE put the edges in $E_{S_{v_1,v_2}\leftrightarrow \{v_1,v_2\}}$ confined by Theorem~\ref{theo:which_affected_insert} into the queue;
                        							\ENDIF
                       					\ELSE
                       								\IF{ $(v_1,v_2)$ is marked }
                       										\STATE unmark the edge $(v_1,v_2)$;
                        									\STATE record the truss number of $(v_1, v_2)$ as unchanged, i.e. $unchanged((v_1, v_2))=true$;
                        									\STATE put the edges in $E_{S_{v_1,v_2}\leftrightarrow \{v_1,v_2\}}$ confined by Theorem~\ref{theo:which_affected_insert} into the queue; 
                        									%\COMMENT{the truss number of $(v_1, v_2)$ is unchanged} 
                        							\ENDIF
                        				\ENDIF
                        				
                        \ENDWHILE
                        \STATE start from the edge $(a,b)$, do a depth-first or breadth-first search: for all marked edges, unmark them and increase the truss numbers by 1;
                        \STATE compute the truss number of the inserted edge $(a,b)$;
             \RETURN $G$;
   \end{algorithmic}
}
\end{algorithm}


\begin{algorithm}[t]
\caption{ $localSupport2((v_1,v_2), k)$ }
\label{algo:localSupport2}
{
\textbf{Input:} an edge $(v_1,v_2)$ and a truss number $k$;\\
\textbf{Output:} the upperbound local support of $(v_1,v_2)$ with respect to the truss number $k$;
  \begin{algorithmic}[1]
            \STATE $lSupport \leftarrow 0$;
            \FOR{ each node $v \in n(v_1)\cap n(v_2)$}\label{line:increaseInter}
            		\IF{ $\phi((v,v_1)) \geq k \wedge unchanged((v,v_1))==false \wedge  \phi((v,v_2)) \geq k  \wedge unchanged((v,v_2))==false$ }
            				\STATE $lSupport \leftarrow lSupport + 1$;
            		\ENDIF
            \ENDFOR
            \RETURN $lSupport$;
   \end{algorithmic}
}
\end{algorithm}

The idea of mark-and-verify approach is that we determine whether the truss number of an edge should be increased in two steps. In the mark step, we try to find which edges may have their truss numbers be increased. An edge is marked if the truss number of the edge is possible to be increased by 1. As the inspection goes on, once we find an edge cannot be updated, we go on checking the neighbor marked edges to see whether there are other marked edges are affected, i.e. do not need to be updated as well. The marking steps and the verifying steps are intertwined. 


The mark-and-verify algorithm is given in Algorithm~\ref{algo:out_insert}. We now explain in detail. Firstly, we insert the edge $(a,b)$ and put the edges in  $E_{S_{a,b}\leftrightarrow \{a,b\}}$ confined by Theorem~\ref{theo:which_affected_insert} into the queue (line 1 and 2). While the queue is not empty (line 3), we take an edge from the queue (line 4), and check whether the condition ``$localSupport2((v_1,v_2),\phi(v_1,v_2)) \geq \phi((v_1,v_2))-1 $ ''. If so, it means the edge $(v_1,v_2)$ may have its truss number increased by 1, because $(v_1,v_2)$ has enough local support at the moment. (Function $localSupport2()$ will be introduced in detail in the next paragraph.) As a result, if $(v_1,v_2)$ has not been identified as possibly-affected, i.e. $(v_1,v_2)$ is not marked (line 6), we mark the edge $(v_1,v_2)$ and put the edges in $E_{S_{a,b}\leftrightarrow \{a,b\}}$ confined by Theorem~\ref{theo:which_affected_insert} into the queue (line 7 and 8). If $(v_1,v_2)$ is marked, nothing needs to be done. We just leave $(v_1,v_2)$ as marked (possibly-affected). On the contrary, if ``$localSupport2((v_1,v_2),\phi(v_1,v_2)) < \phi((v_1,v_2))-1 $ '', it means the edge $(v_1,v_2)$ will keep its truss number unchanged, because it does not have enough local support with respect to the truss number $\phi((v_1,v_2)) + 1$. As a result, if $(v_1,v_2)$ is marked (identified as possibly-affected previously) in line 11, we unmark the edge $(v_1,v_2)$, record the truss number of $(v_1,v_2)$ as unchanged and put the edges in $E_{S_{a,b}\leftrightarrow \{a,b\}}$ confined by Theorem~\ref{theo:which_affected_insert} into the queue (line 12, 13 and 14). Finally, in line 18, for all the left marked edges, we increase their truss numbers by 1, because these are the affected edges. We also need to unmark them eventually to prepare for the maintenance of the next update operation. In line 19, we compute the truss number of the newly inserted edge $(a,b)$. 

%The algorithm is described in Algorithm~\ref{algo:out_insert}. Similarly, we have the description as follows: we firstly insert the edge and put the neighbours of the edge into the queue (line 1 and 2). While the queue is not empty (line 3), we take an edge from the queue (line 4), and check whether the truss of the edge is within the range $[k_{min}, min(|S|+1, k_{max})]$ (line 5), if not, the edge will not be affected, we will inspect the next edge in the queue (line 6). If the current truss number of $(a,b)$ is within $[k_{min}, min(|S|+1, k_{max})]$. We need to check whether it has local support at least $k-1$, if not (line 8), the truss number of the edge must stay as before, this is guaranteed by Lemma~\ref{lemma:insert_mark}. We will then record the truss number of $(a,b)$ as unchanged and check other marked edges since we have known the truss of $(a,b)$ has not changed (line 9). If the edge $(a,b)$ does have enough support at the moment (line 10), we will then mark the edge, meaning the truss number of the edge may or may not increase, but needs a further inspection (line 11). In the end, for all marked edges, we increase the truss by 1 (line 14) and finally we determine the truss number specifically for the newly-inserted edge. The function $enoughSupport()$ is similar to $increaseEdgeTruss()$. The difference is that, in line 4, we count the edge with both neighbours having truss no less than $k$. In such way, we will not miss to update any edge. Even though, some edges may pass the check temporarily, they will be found out later when we gradually find out that some $k$-truss edges cannot be upgraded to $(k+1)$-truss edges.

We now explain the function $localSupport2()$. The function takes an edge $(v_1,v_2)$ and a truss number $k$ as input. Here, $k = \phi(v_1,v_2)$. The function returns an upperbound of the local support $sup((v_1,v_2),T_{\phi(v_1,v_2)+1})$, where $sup((v_1,v_2),T_{\phi(v_1,v_2)+1})$ is the support of the edge $(v_1,v_2)$ in a $(\phi(v_1,v_2)+1)$-truss. In the beginning, all the edges with truss number $k$ have the possibility to become $(k+1)$-truss edges. As a result, $localSupport2((v_1,v_2),k)$ returns the highest bound of $sup((v_1,v_2),T_{\phi(v_1,v_2)+1})$. As the inspection goes on, some edges are found to be not affected, e.g. there may be a node $v \in n(v_1) \cap n(v_2)$ having $unchanged((v,v_1))$ changed to $true$ by Step 13 in Algorithm~\ref{algo:out_insert}. In such a case, the function $localSupport2((v_1,v_2),k)$ will return a smaller value on the next call. As more edges are found to be not affected, the value returned by the function will become smaller. Once the function $localSupport2((v_1,v_2),k)$ returns a value that is less than $k-1$, we can conclude that $(v_1,v_2)$ will not have its truss number increased by 1. Lemma~\ref{lemma:insert_mark} guarantees the conclusion.    

%Our approach is as follows: let $k$ be a truss number within the range $[k_{min}, min(k_{max},|S+1|)$, firstly start from the inserted edge $(a,b)$, check whether the edges in $E_{S\leftrightarrow \{a,b\}}$ with truss number $k$ have local support in the $k$-truss no less than $k-1$. If an edge does have no less than $k-1$ local triangles in the $k$-truss, we need to inspect the edge later. It passes the check at this time, but does not mean its truss number will be updated finally. If not, these edges cannot be in $(k+1)$-truss. This claim is supported by Lemma~\ref{lemma:insert_mark}. If the truss number of an edge is found cannot be updated, i.e. the truss number stays as $k$. We need to go back to check the undecided edges, those previously pass the check to see whether they really need to be updated. 


\begin{lemma}
Let edge $(a,b)$ have the truss number at least $k$, if the local support of $(a,b)$ in the $k$-truss containing $(a,b)$ is smaller than $(k-1)$, then edge $(a,b)$ cannot be in a $(k+1)$-truss.
\label{lemma:insert_mark} 
\end{lemma}

\begin{proof} By contradiction, assume $(a,b)$ can be in a $(k+1)$-truss, then a necessary condition is that the edge should have local support at least $k-1$ in the $(k+1)$-truss. Since a $(k+1)$-truss is also a $k$-truss, it implies that $(a,b)$ must have at least $k-1$ support in the $k$-truss containing $(a,b)$. A contradiction appears. 
%In the extreme case, all $k$-truss edges are $(k+1)$-truss edges. In such case, if the edge $(a,b)$ does not have enough local support, then the edge cannot be in the $(k+1)$-truss. A necessary condition for an edge to be in a $(k+1)$-truss is that the edge should have local support at least $k-1$.
\end{proof}



%Another important aspect of the mark-and-verify method, compared with the naive decomposition based method, is that we can inspect different truss numbers simultaneously. Lemma~\ref{lemma:simultaneous} is supporting this.

%\begin{lemma}
%Following the mark-and-verify approach, truss maintenance can be done simultaneously for different truss numbers. 
%\label{lemma:simultaneous}
%\end{lemma}

%\begin{proof} According to Lemma~\ref{lemma:how_much_effect}, edges with truss number no more than $k-1$ cannot be in $(k+1)$-trusses after one edge insertion. As a result, it is safe to inspect only $k$-truss edges to find the new $(k+1)$-truss edges. The condition holds for every $k$ between $[k_{min}, min(k_{max},|S+1|)$.
%\end{proof}

In the following, we prove Algorithm~\ref{algo:out_insert} is correct and analyze the algorithm complexity.

\begin{lemma}
Algorithm~\ref{algo:out_insert} is correct. The complexity is $O(|E_l|)$, where $|E_l|$ is the number of edges whose local support are affected and $|E_l| << |E|$.
\end{lemma}

\begin{proof}
The first possibly-affected set of edges are put into the queue in line 2. For the other edges, the local support condition ``$localSupport2((v_1,v_2),\phi(v_1,v_2)) \geq \phi((v_1,v_2))-1 $'' and line 6-8 guarantee that all possibly-affected edges will be put into the queue. ``$localSupport2((v_1,v_2),\phi(v_1,v_2)) < \phi((v_1,v_2))-1 $'' and line 11-14 guarantee that once an edge is found to be not affected. The effect will be spread to the full set of other edges.  
%Obviously, the naive truss decomposition method is correct. Algorithm~\ref{algo:out_insert} follows the same idea and can be considered as a guided version of truss decomposition. The inspection started from the inserted edge rather than an arbitrary one. Lemma~\ref{lemma:simultaneous} guarantees the update can be done simultaneously for each $k$.

Complexity of Algorithm~\ref{algo:out_insert}: similar to Algorithm~\ref{algo:out_delete}, the dominating step of Algorithm~\ref{algo:out_insert} is the while clause, from line 3 to line 17. In the while clause, the critical steps are line 5, line 8 and line 14. All of them have complexity $O(|n(v_1)|+|n(v_2)|)$. Again, the complexity of Algorithm~\ref{algo:out_insert} is $O(n_q \cdot deg_{max})$. Different from the deletion case, $n_q$ is bounded by $4|deg_{max}||E_l|$ because the edges in $E_{S_{v_1,v_2}\leftrightarrow \{v_1,v_2\}}$ will be put into the queue when we both mark and unmark the edge $(v_1,v_2)$, while for the deletion algorithm, we only put the edges in $E_{S_{v_1,v_2}\leftrightarrow \{v_1,v_2\}}$ into the queue when we mark the edge. Nevertheless, the worst case complexity of Algorithm~\ref{algo:out_insert} is also $O(|E_l|)$, where we usually have $|E_l| << |E|$.
\end{proof}


\iffalse

\subsubsection{Optimizations}



After seeing the naive method, one may ask can we do better. Then, intuitively we should reduce the size of the graph that we need to inspect.

\subsubsection{Local support materialization}

With local support materialization, we can store the local support on each edge. 

Property: In a $k-truss$ there must be an edge with local support $k-2$, other the $k-truss$ must be a $(k+1)-truss$.


After seeing the naive method, one may ask can we do better. Then, intuitively we should reduce the size of the graph that we need to inspect.

Firstly, store all local support for different $k$ for an edge. And then,  




Critical edges:

First type: local triangles equals to truss number, then they are critical, because local value decrease will result in truss number decrease.

K-truss property:

Property 1: If two $k$-truss share the same edge, they can be merged to form a larger k-truss.

Property 2: If a $k$-truss has a cut point, then the cut point joins  a set of $k$-trusses to form the original $k$-truss. (existing property)

\subsubsection{Closed update property}


For a given $k$ we need to inspect, i.e. $k \in [k_min, min\{|S|+1, k_{max}\}]$ for insertion, $k \in [k_min, k]$ for deletion. The k-truss containing (a,b) can be divided into three parts: a k-truss containing (a,b) denoted as $S_{ab}$, a k-truss containing node a with a as a cut point (if the truss is not empty) denoted as $S_a$, a k-truss containing node b with b as a cut point denoted as $S_b$.

For deletion, only the truss containing (a,b) will be affected. How to find $S_{ab}$? Solution: start from node a, BFS or DFS neighbour edges with truss number $k$, stop expanding for the node b, we can find $S_{ab} + S_b$, similarly find $S_{ab}+S_a$, do an intersection, we got $S_{ab}$.


Question: Can we do the trusses in $[k_{min},k]$ together?

\fi




\section{Query index maintenance}
\label{sect:index}

The ultimate purpose of maintaining truss numbers for each edge is to serve queries. In the real world, a graph is often involving and thus the trusses are changing from time to time. At a particular time, if a user wants to know the current $k$-trusses, it is desired we can answer this query as soon as possible. In this section, we will introduce how maintaining truss numbers for each edge can help answer the queries quickly, and what other maintenance work we need to do, i.e. query index maintenance. 



\subsection{Querying the $k$-trusses}
To find the $k$-trusses from a graph, if we do not have the truss numbers recorded on the edges, we may need to recompute the $k$-trusses from scratch if the graph has been updated since the last query, because the $k$-trusses may change after the updates. Apparently, recomputing the $k$-trusses is very time-consuming, even though some pruning methods can be designed to speed up the process, e.g. pruning the edges that have global support less than $k-2$. On the other hand, if we have the truss numbers recorded and maintained, things will be easier. A simple method is to traverse the graph and group connected edges with truss number $k$ together. Each connected component is then a $k$-truss.


\subsection{Indexing the $k$-trusses}

To avoid traversing the whole graph to answer a $k$-truss query, we can take one edge from a $k$-truss and represent the $k$-truss with the edge which we call a representative. In this way, the $k$-truss containing the representative can be found by performing a depth-first or breadth-first traversal from the representative on the graph. To be specific, let the representative be $e$, in the traversal, when we meet other edges with truss number $\phi(e)$, we include the new edges into the truss containing the representative, and finally we can find a truss with truss number $\phi(e)$. As a result, if we want to know all the $k$-trusses, we just need to find out $k$ edges each of which is in a standalone truss, and then find the trusses by traversing the graph from those edges. That means if there are $t$ $k$-trusses, we can index $t$ edges to represent the $t$ $k$-trusses. 

How to choose a representative? In general, a representative can be chosen randomly. It takes similar cost to find a $k$-truss starting from different representatives within the $k$-truss. 
%However, for deletion-intensive graphs, we suggest to choose an edge with a relatively higher local support as the representative, because the representative is less likely to be downgraded into a $(k-1)$-truss after a few deletions; while for insertion-intensive graphs, we suggest to pick the representative with a relatively lower local support. Nevertheless, it is possible that a ``good'' representative may become not so good after a series of edge updates, because the local support of the edges have changed. In such case, we can replace the existing representative with some better one if we manage to find another better representative candidate during the maintenance process. We will report the effect of representative selection in the experiment part. In the following, without loss of generality, we assume the representatives are selected randomly.
%The advantage of indexing trusses is that to answer truss queries, rather than traverse the whole graph, we can traverse less part of the graph starting from the indexed edges which are proven to be in a $k$-truss. %In particular, the representative edges can be organized into a tree structure. A $k$-truss may contain several $(k+1)$-trusses, so the edges representing $(k+1)$-trusses will be recorded as children of the edge representing $k$-truss. In this way, the edges are organized in a tree structure. We will give an example here. Edge $a$, $b$ represents two $k$-trusses which is $\{e_1, e_2, ..., e_i\}$, $\{e_{i+1}, e_{i+2}, ..., e_j\}$. Both of them are $k+1$-trusses. Edge $c$ represents a $k$-truss which includes the two $(k+1)$-trusses.

\subsection{Maintaining the index}

In this section, we introduce how to maintain the index, i.e. maintain the representatives.

%\subsubsection{Lazy maintenance}
%The idea of lazy maintenance is straightforward. That is we update the representatives after all the truss numbers of the affected edges are updated. 
\subsubsection{Deletion}

Firstly, we discuss a deletion. If a deletion occurs, a number of edges will be affected from the deleted edge $e$. For a particular truss number $k \in [k_{min}(e),\phi(e)]$, there are two types of change related to $k$-trusses: (1) some $(k+1)$-truss edges become $k$-truss edges; (2) some $k$-truss edges become $(k-1)$-truss edges. As to the representatives, there are three cases: (1) some $k$-truss representatives may stay as representatives because their truss numbers stay the same; (2) some $k$-truss representatives may stop being representatives because their truss numbers change to $k-1$; (3) in addition, we may need to add some new representatives into the index to represent some newly generated $k-1$-trusses.  

Consider the original $k$-truss $T_{k}$ containing the deleted edge $e$, after deleting $e$, we may further delete some other edges (starting from $e$) whose truss numbers downgraded to $k-1$ in $T_{k}$. As a result, the updated $T_{k}$ may shrink into a smaller $k$-truss, or may be decomposed into several $k$-trusses, or may even disappear ($T_{k}$ becomes a part of a $(k-1)-truss$). To maintain the representatives for the $k$-trusses, the method is to search the updated $T_{k}$ and choose a representative for each connected component. If a representative is not in the current $k$-truss index, we add the new representative into the index. If a previous representative has the truss number downgraded from $k$ to $k-1$, then remove the representative from the $k$-truss index. In this way, truss index is maintained for deletion.

%We have the following property: if an edge is affected, i.e. the truss of an edge is reduced from $k$ to $k-1$, the edge must be connected with another affected edge also with truss number reduced from $k$ to $k-1$ or connected with the deleted edge. This property can be proved.

For each edge, we can record its representative. For the edges in the non-affected area, if their representatives are deleted, we then choose themselves as representatives, and propagate the information onwards until all the bridges between the non-affected area and the affected area have been examined.  For the affected area, we explore from the deleted edge to find a connected affected area with truss number $k-1$ (the affected area had truss number $k$ before the deletion). If this area is connected with an edge represented by an edge $e_{rep}$ with unchanged truss number $k-1$, then all the edges in the connected affected area will be represented by the representative $e_{rep}$, otherwise, we randomly choose an edge from the connected affected area as a new representative to represent the area. 
%There are two possibilities: the affected edges should merge with existing trusses, or the affected edges become stand-alone trusses.  (1) If the affected edges does not include any representative edges, start from the affected edges for each affected truss number $k' \in [k_{min},k]$, perform a traversal on the whole graph, if the traversal meets an representative edge, that means the affected edges can be found from the representative. The index does not need to be changed. Otherwise, add one of the affected edges of truss number $k'$ into the index representing a new $k'$-truss produced by deletion. (2)If the affected edges include representative edges, check whether there is a $k'$-truss subgraph within the $k'$-truss which has the representative edge affected. If there is a $k'$-subgraph, use a new representative to represent the $k'$-truss, otherwise delete the representative, i.e. delete the $k'$-truss. 
 

%(1) If we did not meet a representative of $k$-truss, then nothing needs to do for the decreased edges, because these edges cannot be found by the existing representatives. For the new $k$-truss edges (those downgraded from $k+1$-trusses), we need to search from these edge to their neighbors if we met an existing $k$-truss edge, we do not need to do anything, because existing representatives can cover the new $k$-truss edges; otherwise, we need to pick an edge from the new edges to be a new $k$-truss representative. It can be proved that the new downgraded $k$-truss edges are connected, so there is at most one new $k$-truss representative.
%(2) If we meet a representative of $k$-truss, it means the current representative will no more be a representative, also a set of previous $k$-truss edges will no long be $k$-truss edges, so we need to find new representatives. It is possible that we need to add more than one representatives. So the method is to search the previous $k$-truss containing the deleted representative, for each connected component, choose a new representative. 

\subsubsection{Insertion}

Secondly, we discuss an insertion. If a insertion occurs, similarly a number of edges will be affected from the inserted edge $e=(a,b)$. For a particular truss number $k \in [k_{min}(e),min(|S_{a,b}|+1, k_{max}(e))]$, there are also two types of change related to the $k$-truss: (1) some $k$-truss edges become $(k+1)$-truss edges; (2) some $(k-1)$-truss edges become $k$-truss edges. For the representatives, (1) some $k$-truss representatives may stay as representatives; (2) some existing $k$-truss representatives may be removed, because, after inserting the edge $e$, some existing $k$-trusses can be merged into a larger $k$-truss, so we only need one edge to represent the larger $k$-truss; finally, we may need to add some new $(k+1)$-truss representatives if there are newly generated $(k+1)$-truss.   

Again, let $T_{k}$ be a $k$-truss before inserting $e$, where $k$ is in the range $[k_{min}(e),min(|S_{a,b}|+1, k_{max}(e))]$, (1) if $k > \phi(e)$, the $k$-truss representatives remain the same, because $e$ is not in any $k$-truss, and thus does not affect the $k$-truss indexes; (2) if $k \leq \phi(e)$, we start from the edge $e$ and traverse the subgraph $T_{k}\cup\{e\}$ by inspecting the connected edges with truss number $k$. During the process, if we meet more than one existing representatives, we keep one of them in the index and delete other representatives from the index. If we do not meet any existing representative, we add one of the edges with truss number $k$ into the index to represent the current $k$-truss. In this way, truss index is maintained for insertion.
%(1) If the affected edges does not include any representative edges, start from the affected edges from each affected truss number $k' \in [k_{min}, min\{k_{max}, |S|+1\}]$, perform a traversal, if the traversal meets a representative edge, then disregard these affected edges, because they can be found by traversing the graph through the representative. Otherwise, begin with higher trusses, traverse the graph from the promoted representative (from $k$ to $k+1$), if an existing $k+1$-truss representative is met, it means the updated edges can be found through an existing $k+1$-truss, we can disregard the updated edges; otherwise we choose an edge as a representative from the updated edges to represent the new $(k+1)$-truss. At the same time, remove the promoted $(k+1)$-truss edges from the existing $k$-truss and choose a new representative for the existing $k$-truss. 

Similarly, for a non-affected area, the truss numbers of the edges are not changed. The edges will be represented by the same edge representatives even though the edge representatives may upgrade from $k$-trusses to $k+1$-trusses. This is because  a $(k+1)$-truss representative can also be a $k$-truss representative, since the representative can be guaranteed to be in a $k$-truss. There may be repeated representatives representing the same connected truss subgraph. The repetition will be resolved when querying the $k$-trusses when repeated representatives will be removed. For the affected area, for $k \in [k_{min}(e), min(|S_{a,b}|+1, k_{max}(e))]$, we do the following: if an affected edge $e'$ has the truss number increased to $k+1$, but the truss number of its representative is still $k$, we change the truss representative of $e'$ into $e'$ itself, and then propagate the effect to the neighbor edges.


\iffalse

Summarize: representative maintenance. For deletion, (1) stay as rep; (2) not rep any more (because of truss reduce); (3) add a new rep (because of truss split). similarly, for insertion, (1) stay as rep; (2) not a rep any more (because of truss merge); (3) add a new rep (because of new truss).

Summarize: truss change. Current truss containing $(a,b)$ will be: for deletion, (1) smaller truss; (2) several trusses; (3) disappear. for insertion, (1) remain the same; (2) two trusses merges; (3) a new $(k+1)$-truss produced.


How to combine the maintenance process seaminglessly with updates.

\fi

\section{Experiments}
\label{sect:experiments}

In this section, we report the performance of the truss maintenance algorithms. All experiments are done on a desktop with Intel(R) Core(TM) i5-2400 CPU at 3.1GHz and 8GB RAM. The operating system is Windows 7 Enterprise, and the code is written in Java.



\subsection{Datasets and Approaches}
We use three datasets to test the algorithms, Epinions social network (soc-Epinions1) \cite{DBLP:conf/semweb/RichardsonAD03}, Enron email network (email-Enron)~\cite{DBLP:journals/corr/abs-0810-1355}, and Slashdot social network (Slashdot0811)~\cite{DBLP:journals/corr/abs-0810-1355}. Epinions social network is a who-trust-whom online social network of a general consumer review site (www.Epinions.com). Members of the site decide whether to trust each other. Enron email communication network covers all the email communication within a dataset of around half million emails, which are collected and published by Federal Energy Regulatory Commission. Slashdot social network is a network that contains friend links between the users of Slashdot. All the above datasets are in Stanford Large Network Dataset Collection\footnote{http://snap.stanford.edu/data/}. We give the details of each dataset in terms of number of vertices, edges, and average degrees in Table~\ref{tab:dataset}. We randomly generated enough number of updates (insertions and deletions) for each dataset and stored them for reuse. We guarantee that when we test different approaches on a particular dataset, we use the same set of updates. The approaches we have compared are listed in Table~\ref{tab:vertexApproach}

\begin{table}[t]
\renewcommand{\arraystretch}{1.3}
\centering
\caption{Datasets}
\label{tab:dataset}
  \begin{tabular}{c|c|c|c}
  \hline
  \hline
  & vertices & edges & maximum truss \\
  \hline
  Epinions network & 75879 & 508837 & 33 \\ 
  
  \hline
  Enron email network & 36692 & 183831 & 22 \\
  \hline
  Slashdot social network & 77360 & 905468 & 34 \\
  \hline
  \hline
  \end{tabular}
\end{table}

\begin{table}[t]
\renewcommand{\arraystretch}{1.3}
\centering
\caption{Summary of the approaches}
\label{tab:vertexApproach}
  \begin{tabular}{l|l}
  \hline
  \hline
  batchUpdate 			& process the updates in a batch mode and \\
  									& do a truss decomposition to find the new \\
  									& $k$-truss \\
  \hline
  progressiveUpdate & maintain the truss number for each edge, \\ 
  									& process the updates on-the-fly and search\\
  									& the graph to find the new $k$-truss \\
  									& using the recorded truss numbers \\  
  \hline
  indexedUpdate 		& maintain the truss number for each edge, \\ 
         						& maintain  truss representatives as an index, \\
         						& process the updates on-the-fly and find \\
         						& the new $k$-truss by searching the graph \\
         						& from the representatives \\
  \hline
  \hline
  \end{tabular}
\end{table}

\subsection{Effect of batchUpdate vs progressiveUpdate}
In this section, we compare the time cost of batchUpdate and progressiveUpdate. The batchUpdate approach stands for processing the updates in a batch and then doing truss decomposition on the graph to find the $k$-truss from the graph. The decomposition starts from smaller truss numbers and stops at the number $k$. The progressiveUpdate approach means that the algorithms introduced in Section~\ref{sect:algorithms} are used to maintain truss numbers while performing updates and the $k$-trusses are evaluated by searching the graph using the truss numbers. Fig~\ref{fig:epinion} shows that progressiveUpdate is much better than batchUpdate when the number of updates is moderate for all the datasets. As the number of updates increase, the gap between batchUpdate and progressiveUpdate decreases. The cost of progressiveUpdate will catch up with batchUpdate when there are 10,000 updates. Fig.~\ref{fig:email} and~\ref{fig:slashdot} have similar trends, but the catch-up points are different.

\begin{figure*}[t]
  \centering
  \subfigure[$k=30$]{\label{fig:epinion30}
    %\includegraphics[scale=0.5]{fig/epinion30.eps}}
    \includegraphics[height=48mm,width=60mm]{epinion30.eps}}
 \hskip 0.5in
  \subfigure[$k=25$]{\label{fig:epinion25}
    \includegraphics[height=48mm,width=60mm]{epinion25.eps}} 
 \hskip 0.5in
  \subfigure[$k=20$]{\label{fig:epinion20}
    \includegraphics[height=48mm,width=60mm]{epinion20.eps}}
  \hskip 0.5in
  \subfigure[$k=15$]{\label{fig:epinion15}
    \includegraphics[height=48mm,width=60mm]{epinion15.eps}}    
\caption{Epinions Social Network}
\label{fig:epinion}
\end{figure*}


\subsection{Effect of index vs non-index}
In this section, we compare the performance of progressiveUpdate and indexedUpdate. Compared with the progressiveUpdate approach, indexedUpdate additionally builds and maintains the truss indexes, i.e. truss representatives. Queries will be answered by traversing the graph from the representatives and the representatives are maintained when processing edge updates. For most datasets, it can be seen that indexedUpdate is better than progressiveUpdate when the number of updates is moderate. As the number of updates becomes larger, indexedUpdate becomes worse than progressiveUpdate, such as the result shown in Fig.~\ref{fig:epinion15},~\ref{fig:email10} and~\ref{fig:slash15}. The reason is probably that indexedUpdates spends more time on maintaining the indexes.      



\subsection{Effect of different truss number $k$}
In this section, we report the effect of different truss number $k$. As we can see, for all datasets, for larger numbers of $k$'s, progressiveUpdate and indexedUpdate are much better batchUpdate, i.e. they can accommodate more updates before they become worse than batchUpdate. For example, for Enron email data, 8,000 updates make progressiveUpdate worse than batchUpdate for $k$=18 (see Fig.~\ref{fig:email18}), while only 6,000 updates make progressiveUpdate worse (see Fig.~\ref{fig:email10}). The reason is that, for a larger $k$, only a small portion of the graph needs to be accessed when processing edge updates. A larger $k$ implies a smaller $k$-truss. For smaller $k$'s, the advantage of progressiveUpdate and indexedUpdate compared to batchUpdate become less obvious.


\subsection{Effect of different datasets}

In this section, we report the effect of different datasets. In Fig.~\ref{fig:slashdot}, for Slashdot data (average clustering coefficient: 0.0555), progressiveUpdate and indexedUpdate are better than batchUpdate up to 16,000 updates for $k$=30, while for Epinions data (average clustering coefficient: 0.1378), progressiveUpdate and indexedUpdate are only better than batchUpdate under around 10,000 updates (Fig.~\ref{fig:epinion30}). The reason is that Slashdot data is relatively sparser and is not a centralized dataset. As a result, the updates are usually done less costly. Epinions data is more centralized than Slashdot data, and thus each update needs to access more nodes. Among the three datasets, Enron email network (average clustering coefficient: 0.4970) is the smallest dataset, on which all the approaches run faster, however, progressiveUpdate and indexedUpdate allow the smallest number of updates before perform worse than the naive batchUpdate approach. Our maintenance approaches work better for decentralized data.


\begin{figure*}[t]
  \centering
  \subfigure[$k=22$]{\label{fig:email22}
    %\includegraphics[scale=0.5]{fig/epinion30.eps}}
    \includegraphics[height=48mm,width=60mm]{email22.eps}}
 \hskip 0.5in
  \subfigure[$k=18$]{\label{fig:email18}
    \includegraphics[height=48mm,width=60mm]{email18.eps}} 
 \hskip 0.5in
  \subfigure[$k=14$]{\label{fig:email14}
    \includegraphics[height=48mm,width=60mm]{email14.eps}}
 \hskip 0.5in
  \subfigure[$k=10$]{\label{fig:email10}
    \includegraphics[height=48mm,width=60mm]{email10.eps}}    
\caption{Enron Email Network}
\label{fig:email}
\end{figure*}

\begin{figure*}[t]
  \centering
  \subfigure[$k=30$]{\label{fig:slash30}
    %\includegraphics[scale=0.5]{fig/epinion30.eps}}
    \includegraphics[height=48mm,width=60mm]{slash30.eps}}
 \hskip 0.5in
  \subfigure[$k=25$]{\label{fig:slash25}
    \includegraphics[height=48mm,width=60mm]{slash25.eps}} 
 \hskip 0.5in
  \subfigure[$k=20$]{\label{fig:slash20}
    \includegraphics[height=48mm,width=60mm]{slash20.eps}}
 \hskip 0.5in
  \subfigure[$k=15$]{\label{fig:slash15}
    \includegraphics[height=48mm,width=60mm]{slash15.eps}}    
\caption{Slashdot Social Network}
\label{fig:slashdot}
\end{figure*}


\section{Related Work}
\label{sect:related}
 
The concept of ``truss'' was firstly introduced by Cohen~\cite{DBLP:journals/web/truss} in 2008, when social networks developed fast and corresponding research prevailed. Compared with other cohesive subgraph models, such as clique~\cite{RePEc:spr:psycho:v:14:y:1949:i:2:p:95-116}, quasi-clique~\cite{DBLP:conf/latin/AbelloRS02, DBLP:journals/tods/ZengWZK07}, $n$-clique~\cite{n_clique}, $n$-clan~\cite{n_clan}, $n$-club~\cite{n_clan}, $k$-plex~\cite{Seidman1978}, $k$-core~\cite{Seidman1983269}, $k$-truss has its own advantage (mentioned in the introduction already). The computation of $k$-truss, also called truss decomposition, has been studied in~\cite{DBLP:journals/web/truss,Cohen:2009:GTM:1591877.1592018,Wang:2012:TDM:2311906.2311909}. Cohen proposed the first truss-decomposition algorithm~\cite{DBLP:journals/web/truss}, which is later outperformed by an improved in-memory algorithm proposed by Wang and Cheng~\cite{Wang:2012:TDM:2311906.2311909}. Wang and Cheng proposed an out-of-memory algorithm for truss decomposition and a top-$t$ $k$-truss evaluation algorithm~\cite{Wang:2012:TDM:2311906.2311909}. Cohen~\cite{Cohen:2009:GTM:1591877.1592018} also proposed a map-reduce based algorithm for truss decomposition. Recently, Zhao and Tung~\cite{DBLP:journals/pvldb/ZhaoT12} studied the truss decomposition problem and consider that the networked data is stored in a graph database. They also studied how to visualize the graph. Different from all the above works, we do not consider finding the trusses from scratch. We aim to maintain the trusses in face of frequent updates. 

Another closely related work to ours is $k$-core maintenance~\cite{DBLP:journals/corr/abs-1207-4567}. Although the ``maintenance'' theme is shared in these two works, the technical solutions are different, because $k$-core and $k$-truss impose requirements on different aspects. To be specific, $k$-core imposes requirements on the nodes, asking each node to connect to at least $k$ other nodes; while $k$-truss imposes requirements on the edges, asking each edge to be in at least $k-2$ triangles. Moreover, in our work, we also discussed how to build $k$-truss indexes and how to maintain $k$-truss indexes. These corresponding questions were not discussed for the $k$-core counterpart in the work~\cite{DBLP:journals/corr/abs-1207-4567}.    
 
All the models above can be considered as explicit models for discovering cohesive structures from networked data. The common feature is that a structure with certain property is predefined, and then the rest work is to design efficient algorithms to discover all the subgraphs with the structure requirement. Another stream is called implicit models, some proposed objective functions first, such as modulariy~\cite{newman-2004-69}, normalized cut~\cite{DBLP:journals/pami/ShiM00}, and then partitioned the graph into a number of parts where the objective functions can be maximized or minimized; Some works defined neighbourhood distance, such as propinquity~\cite{DBLP:conf/kdd/ZhangWWZ09}, structure closeness~\cite{DBLP:conf/kdd/XuYFS07}, and then grouped nearby nodes within a distance threshold around a given node to form a group; Some borrowed the idea of Markov Clustering~\cite{DBLP:conf/kdd/SatuluriP09, DBLP:journals/jgaa/PonsL06} to repeat \emph{random walk} for a few rounds until self-organized clusters turn up. The maintenance problem for implicit models are not studied as well.  

  
 
%Graph connectivity is a fundamental subject in graph theory. Graph connectivity is closely related to minimum cut, since the minimum cut gives the graph connectivity. A large number of have been done on the design of minimum-cut algorithm~\cite{DBLP:conf/soda/HaoO92, DBLP:journals/siamdm/NagamochiI92, DBLP:journals/jacm/StoerW97}.
%A classical problem related to community detection is graph partitioning~\cite{1970}. Its problem is to specify the number of communities in advance. To avoid producing trivial communities, the approximate size of the expected community has to be given as input parameter. The above two aspects are supposed to be crucial factors for a successful community detection algorithm. Another class of algorithms iteratively remove the edges lying between communities. The key point is to define edge centrality, which reflects the possibility of an edge lying between communities. Several centrality definitions were proposed in the literature: edge betweenness, current-flow betweenness, random walk betweenness~\cite{girvan-2002-99}. Flake et al.~\cite{DBLP:journals/im/FlakeTT03} developed a min-cut algorithm based on min-cut trees which is able to produce an arbitrary number of clusters, and can be expanded to produce a hierarchical clustering. A common problem with graph partitioning techniques is that an external decision must be made to indicate when to stop bisecting, that is how many communities exist in the graph~\cite{newman-2004-69}. A Min-max cut based community discovery algorithm was proposed in~\cite{DBLP:conf/icdm/DingHZGS01}. Zhou et al.~\cite{DBLP:journals/pvldb/ZhouCY09} took attribute information into account when finding community. Their algorithm is based K-Medoids clustering, but a potential drawback is too many additional edges may be introduced. The performance of the algorithm will be influenced.


\section{Conclusions and Future Work}
\label{sect:conclusion}

In this paper, we have studied how to maintain trusses in an evolving network by considering edge deletions and insertions. For one edge deletion or insertion, we have investigated the properties of truss change, proposed algorithms to perform truss maintenance and introduced techniques to maintenance truss index updates. In the experiments, we have shown that maintaining truss on-the-fly is more efficient compared to performing batch edge updates and then doing truss decomposition if the update number is not large. We have also shown that having truss indexes and maintaining truss indexes are superior than evaluating truss queries without index support for moderate update frequency. As far as we can see, one direction for future work is to process data that cannot fit into memory, e.g., a $k$-truss may be very large when $k$ is small.   
%In this paper, we have discussed how to find maximal k-edge-connected subgraphs from large graphs. We have proposed a basic cut-based approach and develop several important speed-up techniques: vertex reduction, edge reduction and optimizing the cut algorithm. We have conducted extensive experiments to test the performance of the speed-up techniques. Compared with the basic approach, experimental results show that using speed-up methods can dramatically improve the performance. Vertex reduction is very effective when there are suitable materialized views, because the size of the original graph can be reduced significantly. The effect of edge reduction is moderate, not remarkable, because after discovering the $k$-connected components, we still need to find maximal $k$-connected subgraphs from those $k$-connected components.% And the number of iterations for edge reduction should be small. Generally, 1 or 2 iterations achieve the best.
%The cut pruning is very effective, and it is also easy to implement. One direction for future work is to design external memory algorithms to find maximal $k$-connected subgraphs from massive graphs, because %data is exploding nowadays and some real graphs are too large to fit into memory. %Another interesting direction is to use existing data mining approach to discover some dense subgraphs as the starting points, but how to guarantee the starting points are k-connected needs to be carefully considered.

%\section*{Acknowledgments}
%This work is supported by the grant of Australian Research Council Discovery Project No. DP120102627 and the grant of Research Grants Council of Hong Kong SAR, No. 419109. 
%We would like to thank anonymous reviewers for their helpful comments.


  \iffalse

In this paper, we have proposed a novel model, maximal induced $k$-edge-connected subgraphs, to model communities. We have shown the advantages of this model over existing explicit and implicit models. We have also given out an algorithm to find all maximal induced $k$-edge-connected subgraphs from a given graph. Several pruning techniques and an important graph reduction technique are introduced to speed up the basic algorithm.

In our future work, it will be interesting to test our algorithms on real datasets, such as DBLP data, gene network, to see the actual performance. Another significant but tough task is to compare the quality of different community models. It is tough because it needs the participation of human beings, and may involve a large amount of survey from different domains, because different models may fit specially for different domains. We plan to study a few representative models and compare them in a few selected domains.

  \fi



%\end{document}  % This is where a 'short' article might terminate

%ACKNOWLEDGMENTS are optional
%\section{Acknowledgments}
%This work was supported by the Australian Research Council Discovery Project under the grant number DP0878405.

% The following two commands are all you need in the
% initial runs of your .tex file to
% produce the bibliography for the citations in your paper.
%\bibliographystyle{IEEEtran}
%\bibliographystyle{abbrv}
\bibliographystyle{unsrt}
\bibliography{sigproc}  % sigproc.bib is the name of the Bibliography in this case
% You must have a proper ".bib" file
%  and remember to run:
% latex bibtex latex latex
% to resolve all references
%
% ACM needs 'a single self-contained file'!
%
%APPENDICES are optional
%\balancecolumns


%\newpage
%\appendix


%We give the SW algorithm in Algorithm~\ref{algo:MinimumCut} and~\ref{algo:MinimumCutPhase} and introduce it briefly. Algorithm~\ref{algo:MinimumCut} is the outer loop, runs $|V|-1$ times, because after each loop, $|V|$ will be decreased by 1, for the reason that two vertices are merged into one after each loop (see line 5 in Algorithm~\ref{algo:MinimumCutPhase}). In each loop from line 2 to line 8 in Algorithm~\ref{algo:MinimumCut}, it finds a new min-cut for the current graph (line 3), and compare it with the current cut. A smaller cut will be recorded. At the end of this algorithm, the recorded cut will be the minimum cut. The key steps are in Algorithm~\ref{algo:MinimumCutPhase}. It first selects a seed vertex, and repeatedly take out other vertices from $|V|$ to join the seed vertex. In each round, the vertex having the highest connectivity with the seed set is selected and removed from $|V|$. In the end, the cut of the phase is the edge set $E'_{cut}$ between the last added vertex $v_{last}$ and the rest vertices $V-\{v_{last}\}$. The last two vertices added into the seed set will be merged before the current procedure return to the main loop.

\iffalse

\begin{algorithm}[tbhp]
%\SetLine
\caption{ MinimumCut(G) }
\label{algo:MinimumCut}
{
 \textbf{Description:} find a minimum cut for graph $G$ \\
 \textbf{Input:} a graph $G(V,E)$; \\
 \textbf{Output:} a min-cut edge set $E_{cut}$;
  \begin{algorithmic}[1]
                \STATE initialize $E_{cut} = V$;
                \WHILE{ $|V|$ > 1 }
                        \STATE $E'_{cut}$= MinimumCutPhase(G);
                        \IF{ $|E_{cut}| > |E'_{cut}|$ }
                                \STATE $E_{cut} = E'_{cut}$;
                        \ENDIF
                \ENDWHILE
                \RETURN $E_{cut}$
   \end{algorithmic}
}
\end{algorithm}


\begin{algorithm}[tbhp]
%\SetLine
\caption{ MinimumCutPhase(G) }
\label{algo:MinimumCutPhase}
{
 \textbf{Description:} find an $s$-$t$ cut and merge two vertices \\
 \textbf{Input:} a graph $G(V,E)$ \\
 \textbf{Output:} the edge set incident on $v_{last}$;
  \begin{algorithmic}[1]
                \STATE randomly choose a vertex $v$, and let $A =\{v\}$;
                \WHILE{ $A \neq V$ }
                        \STATE add into $A$ the most tightly connected vertex from $V$;
                \ENDWHILE
                \STATE merging the last two vertices added into $A$;
                \RETURN the edge set $E'_{cut}$ between the last added vertex $v_{last}$ and the rest vertices $V-\{v_{last}\}$;
   \end{algorithmic}
}
\end{algorithm}

 \fi


  \iffalse

\begin{algorithm}[tbhp]
%\SetLine
\caption{ Forest algorithm }
\label{algo:forest}
{
 \textbf{Description:} Let $r(v):=i$ denote that $v$ has been reached by an edge of the forest $F_i=(V,E_i)$. \\
 \textbf{Input:} a graph $G = (V,E)$, \\
 \textbf{Output:} $E_1, E_2, \cdots, E_{|E|}$;
  \begin{algorithmic}[1]
                \STATE Label all nodes $v \in V$ and all edges $e \in E$ ``unscanned";
                \STATE $r(v):=0$ for all $v \in V$;
                \STATE $E_1 := E_2 := \cdots := E_{|E|} := \emptyset$;

                \WHILE{ there exist ``unscanned" nodes }
                        \STATE choose an ``unscanned" node $x \in V$ with the largest $r$;
                        \FORALL { node $y$ adjacent to $x$ by an ``unscanned" edge $e$ }
                                \FORALL {``unscanned" edge $e \in E_{xy}$ }
                                        \STATE $E_{r(y)+1} := E_{r(y)+1} \cup {e}$;
                                        \STATE $r(y):= r(y)+1$;
                                        \STATE Mark $e$ ``scanned";
                                \ENDFOR
                                \STATE Mark $x$ ``scanned";
                        \ENDFOR
                \ENDWHILE
   \end{algorithmic}
}
\end{algorithm}

  \fi

 \iffalse
%Appendix A
\section{Headings in Appendices}
The rules about hierarchical headings discussed above for
the body of the article are different in the appendices.
In the \textbf{appendix} environment, the command
\textbf{section} is used to
indicate the start of each Appendix, with alphabetic order
designation (i.e. the first is A, the second B, etc.) and
a title (if you include one).  So, if you need
hierarchical structure
\textit{within} an Appendix, start with \textbf{subsection} as the
highest level. Here is an outline of the body of this
document in Appendix-appropriate form:
\subsection{Introduction}
\subsection{The Body of the Paper}
\subsubsection{Type Changes and  Special Characters}
\subsubsection{Math Equations}
\paragraph{Inline (In-text) Equations}
\paragraph{Display Equations}
\subsubsection{Citations}
\subsubsection{Tables}
\subsubsection{Figures}
\subsubsection{Theorem-like Constructs}
\subsubsection*{A Caveat for the \TeX\ Expert}
\subsection{Conclusions}
\subsection{Acknowledgments}
\subsection{Additional Authors}
This section is inserted by \LaTeX; you do not insert it.
You just add the names and information in the
\texttt{{\char'134}additionalauthors} command at the start
of the document.
\subsection{References}
Generated by bibtex from your ~.bib file.  Run latex,
then bibtex, then latex twice (to resolve references)
to create the ~.bbl file.  Insert that ~.bbl file into
the .tex source file and comment out
the command \texttt{{\char'134}thebibliography}.
% This next section command marks the start of
% Appendix B, and does not continue the present hierarchy
\section{More Help for the Hardy}
The sig-alternate.cls file itself is chock-full of succinct
and helpful comments.  If you consider yourself a moderately
experienced to expert user of \LaTeX, you may find reading
it useful but please remember not to change it.
%\balancecolumns % GM June 2007
% That's all folks!

 \fi


\end{document}




%-------------------------------------------------------------------------------------------------

\iffalse

\begin{algorithm}[t]
%\SetLine
\caption{ A mark-and-verify truss maintenance algorithm for edge insertion}
\label{algo:out_insert}
{ 
\textbf{Input:} a graph $G=(V,E)$ with truss numbers associated with its edges, a to-be-inserted edge $(a,b)$ \\
 \textbf{Output:} $G=(V,E \cup \{(a,b)\})$ with updated truss numbers associated with its edges 
  \begin{algorithmic}[1]
  					\STATE insert edge $(a,b)$;
            \STATE put the edges in $E_{S_{a,b}\leftrightarrow \{a,b\}}$ confined by Theorem~\ref{theo:which_affected_insert} into a queue;
                        \WHILE{the queue is not empty}
                        				\STATE take an edge $(v_1,v_2)$ from the queue;
                        				\IF{ $(v_1,v_2)$ is not marked $\wedge$ $localSupport((v_1,v_2),\phi(v_1,v_2)) \geq \phi((v_1,v_2))-1 $ }\label{line:increaseS}
                        							\STATE mark the edge $(v_1,v_2)$;
                        							\STATE put the edges in $E_{S_{v_1,v_2}\leftrightarrow \{v_1,v_2\}}$ confined by Theorem~\ref{theo:which_affected_insert} into the queue;
                       					\ELSE
                       								
                        							\STATE record the truss number of $(v_1, v_2)$ as unchanged;
                        							\STATE and check the marked edges (undecided edges) in $E_{nb(v_1)\cap nb(v_2)\leftrightarrow \{v_1,v_2\}}$; 
                        							\\ \COMMENT{the truss number of $(v_1, v_2)$ is unchanged} 
                        				\ENDIF
                        				
                        \ENDWHILE
                        \STATE start from the edge $(a,b)$, do a depth-first or breadth-first search: for all marked edges, unmark them and increase the truss numbers by 1;
                        \STATE compute the truss number of the inserted edge $(a,b)$;
             \RETURN $G$;
   \end{algorithmic}
}

\end{algorithm}


\fi

\section{introduction}


One interesting problem, drawing many researchers' attention recently, is how to find communities from a large graph. For example, in social network analysis, a community may be a group of people who are close friends or share a common interest. In bioinformatics, a community could be a set of genes or proteins within the same functional module. In web analysis, a community could be a collection of web pages dealing with related topics. Finding such communities has significant impact on information dissemination, biomedical exploration, knowledge base buildup and etc.

A community from a graph is generally considered as a subgraph, which are densely connected, but have few links to vertices outside the subgraph. However, to establish a universally agreed definition for community is difficult. We classify the existing works into two categories based on how to model a community: explicitly or implicitly. In explicit models, users are aware of what type of structure a community has. For example, cliques can be used to explicitly model communities, since a clique is a fully connected subgraph, which conveys high relevance within a community. However, cliques may be too strict, because, in many real scenarios, it is unlikely that every entity would have a link to every other entity within the community. Therefore relaxed forms of clique, like quasi-clique (defined on nodes~\cite{DBLP:journals/tods/ZengWZK07} or edges~\cite{DBLP:conf/latin/AbelloRS02}), are proposed and have been studied. On the other hand, a majority of works fall into the other category, implicit models: Some propose objective functions first, such as modulariy~\cite{newman-2004-69}, normalized cut~\cite{DBLP:journals/pami/ShiM00}, and then partition the graph into a number of communities, here a good partition usually maximizes or minimizes the objective functions; Some works define neighbourhood distance, such as propinquity~\cite{DBLP:conf/kdd/ZhangWWZ09}, structure connectivity~\cite{DBLP:conf/kdd/XuYFS07}, and then group nearby nodes within a distance threshold around a given node to form a community; Some borrow the idea of Markov Clustering~\cite{DBLP:conf/kdd/SatuluriP09, DBLP:journals/jgaa/PonsL06} to repeat \emph{random walk} for a few rounds until self-organized communities turn up. Note that there are many implicit models, we just mentioned a few above.


In spite of many choices from implicit models, we would vote for explicit models on account of the following reasons: (I) Easier for users to harness: Users always have a general picture on how the discovered communities will look like. Users are not required to be familiar with the mathematical models or sophisticated parameter setting and adjustment. While many implicit approaches do not provide explicit, clear and easy-to-understand definitions for a community to be discovered. (II) Most implicit models transform community discovery problem into complex optimization problems, which are intrinsic NP-hard problems. Some explicit models may imply expensive mining process as well, but generally speaking, implicit models are more likely to have less efficient solution.


As a result, an explicit model implying an efficient discovering solution is highly sought after. Current explicit models are few and limited. The most representative work is quasi-clique based model, some other explicit models like k-plexes~\cite{Seidman1978}, k-cores~\cite{Seidman1983269} are similar to quasi-cliques. However, in a $\gamma$-quasi-clique, there is a strong restriction that $\gamma$ must be no less than 0.5, i.e., a member is required to connect to at least half of the other members in the community in order to guarantee the quasi-clique is connected. If a community has 100 members, we must ask each member to have direct associations with no less than 50 other members. This condition is obviously too strong. Sometimes, a member with more than 20 links with other members within a community may have shown a strong connection. Furthermore, listing quasi-cliques seems not an easy problem, since listing maximum cliques is of exponential time, even hard to approximate. We will unfold this point in Section~\ref{subsect:property}.


In this paper, we will propose a novel explicit model to model community. We consider communities as \emph{maximal induced k-edge-connected subgraphs}, here $k$ is the edge connectivity of the community subgraph. This model is less restrictive than the quasi-clique model, and has an explicit parameter $k$. We will analyze the merits of the model, and develop algorithms for discovering maximal induced k-edge-connected subgraphs.
When an input graph is large and dense, it may not be applicable to use our basic solution directly, since a dense large graph may slow down the computation significantly. To cope with this challenge, we devise an effective pruning step to reduce the input graph to a reasonable scale.

We summarize our contributions as follows:
\begin{itemize}
    \item We propose a novel model, induced $k$-edge-connected subgraph, to model communities. Comparing with implicit models, the new model is more friendly, sensible, and controllable to users; and comparing with a representative existing explicit model, the new model tends to capture more possible results.

    \item We give out the computational solution to find communities defined by the induced $k$-edge-connected subgraph semantics, including a basic algorithm containing a $O(|V||E|+|V|^2 \log|V|)$ minimum cut algorithm with early-stop property, together with several important optimizations. We also point out a preprocessing strategy that can effectively prune the input graph when the input graph is dense and large.
\end{itemize}

Here is a roadmap of this paper. In Section~\ref{sect:prel}, we give out the formal definition of the problem and introduce some necessary notations. In Section~\ref{sect:disc}, we argue the advantages of our model, and propose an algorithms to correctly find induced $k$-edge-connected subgraphs. We also develop several optimizations for the basic algorithm and point out a preprocessing technique that can reduce the input graph effectively. Related works and final conclusions are stated in Section~\ref{sect:related} and Section~\ref{sect:conclusion} respectively.







\section{Community discovery}
\label{sect:disc}
In this section, we first show the advantages of the induced $k$-edge-connected subgraph model over existing models on modeling the communities. We then propose a basic algorithm to find induced $k$-edge-connected subgraphs based on any minimum cut algorithm. We also point out an efficient min-cut algorithm that is suitable to solve this problem, and give out some optimizing tricks for the basic algorithm. Finally, we propose how to do a preprocessing step so that the size of the graph can be reduced dramatically before carrying on the basic algorithm.
\subsection{Merits of Induced k-edge-connected subgraph}
\label{subsect:property}

In Section~\ref{sect:prel}, we introduced the concept of induced $k$-edge-connected subgraph. We now show the merits of the new model over existing models on describing community structure. The merits include both semantic expressiveness corresponding to the effectiveness of the model at the concept level, and the computational advantages relating to the efficiency of using this model in practice. The details are listed as follows:

\textbf{More Reasonable:} Induced $k$-edge-connected subgraph is more general and can capture more reasonable results, comparing with the existing representative explicit model, quasi-clique~\cite{DBLP:journals/tods/ZengWZK07}. We illustrate this point using an example.

\begin{example}
\label{exam:clique}
In Fig.~\ref{fig:clique} (a), the 8-node graph is likely to be considered as a community, since the nodes are somehow closely related to each other. Unfortunately, this community is not captured by $\gamma$-quasi-clique model,  because $\gamma \geq 0.5$ is required in that model. The reason of imposing this condition ($\gamma \geq 0.5$) is to guarantee that a $\gamma$-quasi-clique is connected. Comparing Fig.~\ref{fig:clique} (a) and (b), they are both 3/8-quasi-cliques; for both graphs, each vertex is connected to three other vertices. The only difference is that (b) is disconnected, and thus not proper to be considered as a community. By setting $\gamma \geq 0.5$, we can avoid the false positives like (b), but we will also miss some reasonable results like (a).
\end{example}

Example~\ref{exam:clique} reminds us the importance of connectivity in a community subgraph. Rather than inspect the degree of each node like the quasi-clique model, we focus on inspecting the connectivity of the community graph. Our argument is based on the fact that a community should be densely connected itself, not including the case that one or a few bridges connecting several densely connected components together. Fig.~\ref{fig:clique} (c) shows one such example. Subgraphs $G[\{A,B,C,D,E,F\}]$ and $G[\{A',B',C',D',E',F'\}]$ should be considered as two communities, although each node in (c) connects to enough many ($\geq 5$) other nodes. As a result, connectivity should be an unignorable aspect.
%(better to have a real example here with one or two bridges)

\begin{figure}[t]
    \centering
    {\includegraphics[width=85mm]{compareWithClique2.eps}}
    \caption{The drawback of clique-based models}
    \label{fig:clique}
\end{figure}

%may need some more comparisons with other explicit models, such 2-hop-clique

\textbf{More Usable} Induced $k$-edge-connected subgraph is more user-controllable. It has only one parameter $k$ to adjust, and users are aware of the meaning of this parameter. While, in the existing implicit models, the physical meaning of their parameters are not very obvious, e.g., the inflation parameter $r$ in Markov clustering algorithm~\cite{DBLP:conf/kdd/SatuluriP09}, propinquity thresholds $\alpha$, $\beta$ in~\cite{DBLP:conf/kdd/ZhangWWZ09}. Furthermore, there may be a few parameters not orthogonal to each other, e.g., close-neighbor number bound $\mu$ and similarity threshold $\epsilon$ in~\cite{DBLP:conf/kdd/XuYFS07}. It is unlikely for users to have complete control on their discovering process unless they get enough acquaintance with the model they are using. And most of the time, they have to wait for the result and check whether the parameter setting is proper. Sometimes, senior or experienced users need to be available to consult with, otherwise they need to run the algorithms on a dataset for several rounds in order to find out a good parameter setting after comparing the output results. When a dataset is large, one run of the algorithms on the dataset may take a long time, and moreover different datasets may require different parameter settings. When a dataset is evolving, i.e. ties between nodes are established or broken down, it is unclear whether and how the parameter settings should be changed accordingly.

As a result, it is obvious to see that induced $k$-edge-connected subgraph is more user friendly than implicit models, though simpler. At least, it can be used as a starting point to give users a rough idea on what the communities may be and also to guide the parameter settings with some initial results if the users still insist to use some sophisticated implicit models to find the communities.

\textbf{Algorithm convergence} Many community discovery algorithms follow a heuristic mining process. It is not clear, at least not proved, whether these algorithms are able to converge, though some works (like~\cite{DBLP:conf/kdd/ZhangWWZ09,newman-2004-69}) claim that they did converge on most datasets. While using induced $k$-edge-connected subgraph to model community, finding those highly connected subgraphs can be proved to be a converging process. We will show this point in later sections.

\textbf{Lower Computational Complexity} Currently, most community models do not imply efficient discovering algorithms. Eg. for the explicit clique-based models, it is widely known that the problem of listing maximum cliques is of exponential time, even hard to approximate. Similarly, the problem for relaxed quasi-cliques should be even harder. As to implicit models, community discovery problem is often NP-hard as well, because it is often transformed into a complex optimization problem, and to find the global optimal solution is NP-hard. Most of the time, heuristics are used to find a local optimal and to speed up the computation. However, using induced $k$-edge-connected subgraph to represent communities, the time complexity of the discovering algorithm is of polynomial time. In fact, by using several optimizations and preprocessing reduction, the mining process is very efficient. We will elaborate this point in the following sections.

%The following advantages are not included in this paper:

%extendability (model can be modified to be more complicated, such as including weights, direction not suitable, multi-edge allowed, loop not allowed)

%maintainability (dynamically with regard to data change) not developed yet

%speed up methods (the use of materialized views, indexes)

\subsection{Induced k-edge-connected subgraph discovery}

In this section, we propose the solution for finding induced $k$-edge-connected subgraphs. We first give a basic solution by using any minimum cut algorithm, and then we point out a specific minimum cut algorithm suitable to solve this problem and also give out several pruning techniques that may dramatically improve the algorithm performance.

\subsubsection{Basic solution}
To find induced $k$-edge-connected subgraphs, we can firstly apply any minimum cut algorithm to the graph to partition the input graph into connected subgraphs by removing the cut. And we repeatedly apply the min-cut algorithm on the produced connected components until the minimum cut of some connected component is at least $k$. The final result is: every connected component is either a single node or a $k$-edge-connected subgraph. As a result, those connected components having connectivity no less than $k$ are regarded as communities. Algorithm~\ref{algo:basic} describes the process.

\begin{algorithm}[t]
%\SetLine
\caption{ Basic Algorithm }
\label{algo:basic}
{
% \textbf{Description:} To find a minimum cut for graph $G$ \\
 \textbf{Input:} a graph $G$, cut threshold $k$  \\
 \textbf{Output:} connected components $R$;
  \begin{algorithmic}[1]
            \STATE $R_0 := \{G\}$;
                        \FORALL{subgraph $G_1(V_1,E_1)$ ($|V_1|\neq 1$) in $R_0$}
                                \STATE find a minimum cut $E_{cut}$ of $G_1$ using any minimum cut algorithm;
                                \IF{ $|E_{cut}| < k$ }
                                            \STATE cut $G_1$ into $G_2$, $G_3$ through min-cut;
                                            \STATE $R_0 := R_0 \cup \{G_2, G_3\} - \{G_1\}$;
                                \ELSE
                                            \STATE $R := R \cup \{G_1\}$;
                                \ENDIF
%                               \IF{ $R_0 = \emptyset $ }
%                                           \STATE break;
%                               \ENDIF
                        \ENDFOR
                \RETURN $R$;
   \end{algorithmic}
}
\end{algorithm}

In algorithm~\ref{algo:basic}, $R_0$ stores the intermediate results for the graph decomposition, i.e. the produced connected components. If a produced connected component $G_1$ is at least $k$-connected, it will be added into the result set $R$ (line 8); if not, $G_1$ will be cut into two pieces $\{G_2,G_3\}$ and added into $R_0$ for later inspection (line 5-6). Some readers may have noticed that an unpromising connected component may be found earlier, not needed to be cut into a few single nodes. Such speed-up tricks will be discussed in Section~\ref{subsect:optimize}.

It is easy to see that Algorithm~\ref{algo:basic} will terminate (exhibiting the third property in Section~\ref{subsect:property}). By Lemma~\ref{lemm:correct}, Algorithm~\ref{algo:basic} can be find all maximal induced $k$-connected subgraphs from $G$ correctly. The reason is that connectivities between different communities are less than $k$, and hence corresponding edges will be finally removed by Algorithm~\ref{algo:basic}, with only community subgraphs left.

\begin{lemma}
Let $G_1(V_1,E_1)$ and $G_2(V_2,E_2)$ be two maximal induced $k$-edge-connected subgraph of $G$, and let $E_{cut}$ be the set of edges in $G$ between the vertices in $V_1$ and the vertices in $V_2$, then $|E_{cut}| < k$.
\label{lemm:correct}
\end{lemma}

\begin{proof}
If $E_{cut} \geq k$, then let graph $G_0$ be $(V_1 \cup V_2, E_1 \cup E_2 \cup E_{cut})$, we have that removing any $k-1$ edges in $G_0$ does not make the resulting graph disconnected, because at least one edge of $E_{cut}$ will remain unremoved, and remove any $k-1$ edges in $G_1$ (or $G_2$) does not make $G_1$ (or $G_2$) disconnected. As a result, we have that $G_0$ is a $k$-edge-connected subgraph, and hence $G[V_1 \cup V_2]$ is at least an induced $k$-edge-connected subgraph. This contradicts with the assumption that $G_1$ and $G_2$ are maximal induced $k$-edge-connected subgraph.
\end{proof}

\subsubsection{A suitable cut algorithm}

It is easy to observe that line 3 in Algorithm~\ref{algo:basic} is the key step to affect algorithm performance. A careful reader may have found that it is not a must to find a minimum cut in line 3. \emph{Any} cut $E'_{cut}$ with $|E'_{cut}|< k$ can be used to cut $G_1$, and guarantee the correctness of the algorithm. So what is a desirable min-cut algorithm for our problem then? We advocate the min-cut algorithm due to Stoer and Wagner~\cite{DBLP:journals/jacm/StoerW97}, denoted by the SW algorithm, which provides an early-stop property, and is also reasonably efficient and easy to implement. We now explain it in detail.

The SW algorithm solves the minimum cut problem using $|V|-1$ minimum $s$-$t$ cut computations. A $s$-$t$ cut is the minimum cut for graph $G$, which can separate vertex $s$, $t$ into two different connected components. The global minimum cut is the lowest value among the $|V|-1$ $s$-$t$ cuts. Return to our problem, if any $E_{c}$ among these $|V|-1$ cuts satisfying $|E_{c}| < k$, we can stop finding other $s$-$t$ cuts on $G_1$ and separate $G_1$ into two connected components safely using $E_c$. We refer this property as early-stop property. Furthermore, the SW algorithm has good theoretical complexity at $O(|E||V| + |V|^2 \log |V|)$. It is not a flow-based algorithm, and is easy to implement. We have assumed readers are familiar with the SW algorithm in~\cite{DBLP:journals/jacm/StoerW97}, otherwise readers are encourage to refer to the original paper or go to in Appendix for a quick review on the algorithm and how it can be combined with Algorithm~\ref{algo:basic}.

  \iffalse

We give the SW algorithm in Algorithm~\ref{algo:MinimumCut} and~\ref{algo:MinimumCutPhase} and introduce it briefly. Algorithm~\ref{algo:MinimumCut} is the outer loop, runs $|V|-1$ times, because after each loop, $|V|$ will be decreased by 1, for the reason that two vertices are merged into one after each loop (see line 5 in Algorithm~\ref{algo:MinimumCutPhase}). In each loop from line 2 to line 8 in Algorithm~\ref{algo:MinimumCut}, it finds a new min-cut for the current graph (line 3), and compare it with the current cut. A smaller cut will be recorded. At the end of this algorithm, the recorded cut will be the minimum cut. The key steps are in Algorithm~\ref{algo:MinimumCutPhase}. It first selects a seed vertex, and repeatedly take out other vertices from $|V|$ to join the seed vertex. In each round, the vertex having the highest connectivity with the seed set is selected and removed from $|V|$. In the end, the cut of the phase is the edge set $E'_{cut}$ between the last added vertex $v_{last}$ and the rest vertices $V-\{v_{last}\}$. The last two vertices added into the seed set will be merged before the current procedure return to the main loop.



\begin{algorithm}[t]
%\SetLine
\caption{ MinimumCut(G) }
\label{algo:MinimumCut}
{
 \textbf{Description:} find a minimum cut for graph $G$ \\
 \textbf{Input:} a graph $G(V,E)$; \\
 \textbf{Output:} a min-cut edge set $E_{cut}$;
  \begin{algorithmic}[1]
                \STATE initialize $E_{cut} = V$;
                \WHILE{ $|V|$ > 1 }
                        \STATE $E'_{cut}$= MinimumCutPhase(G);
                        \IF{ $|E_{cut}| > |E'_{cut}|$ }
                                \STATE $E_{cut} = E'_{cut}$;
                        \ENDIF
                \ENDWHILE
                \RETURN $E_{cut}$
   \end{algorithmic}
}
\end{algorithm}


\begin{algorithm}[t]
%\SetLine
\caption{ MinimumCutPhase(G) }
\label{algo:MinimumCutPhase}
{
 \textbf{Description:} find an $s$-$t$ cut and merge two vertices \\
 \textbf{Input:} a graph $G(V,E)$ \\
 \textbf{Output:} the edge set incident on $v_{last}$;
  \begin{algorithmic}[1]
                \STATE randomly choose a vertex $v$, and let $A =\{v\}$;
                \WHILE{ $A \neq V$ }
                        \STATE add into $A$ the most tightly connected vertex from $V$;
                \ENDWHILE
                \STATE merging the last two vertices added into $A$;
                \RETURN the edge set $E'_{cut}$ between the last added vertex $v_{last}$ and the rest vertices $V-\{v_{last}\}$;
   \end{algorithmic}
}
\end{algorithm}

  \fi

%In presence of many deterministic minimum cut algorithms, Chekuri et al.~\cite{DBLP:conf/soda/ChekuriGKLS97} showed the algorithms in~\cite{DBLP:conf/soda/HaoO92} and~\cite{DBLP:journals/siamdm/NagamochiI92} are faster in practice, and may be good candidates to resort to.

\subsubsection{Pruning techniques}
\label{subsect:optimize}

There are several pruning techniques that can dramatically improve the algorithm performance. We first list them and then explain the rationale afterwards.
Let $G_1(V_1,E_1)$ be a connected component, $\Delta(G_1)$, $\delta(G_1)$ be the maximum and minimum node degree in $G$, $v$ be a node in $G$.

\begin{enumerate}
    \item When $G_1$ is simple and $|V_1| \leq k$, i.e. a connected component has no more than $k$ nodes, the component does not have induced $k$-edge-connected subgraphs, and hence can be disregarded.
%Because, even a complete graph with $k$ nodes is
    \item When $\Delta(G_1) < k$, i.e. the maximum degree of the nodes in the connected component $G_1$ is less than $k$, it reflects that the component does not have induced $k$-edge-connected subgraphs.
    \item If a node $v$ in $G_1$ has $deg(v) < k$, node $v$ can be disregarded from the component. $G_1[V_1-\{v\}]$ may still have induced $k$-edge-connected subgraphs.
    \item If $\delta(G_1) \geq k$, and $\delta(G_1) >= \left\lfloor |V_1|/2 \right\rfloor$, then the connected component $G_1$ is $k$-edge-connected. We do not need to apply the min-cut algorithm on $G_1$.
\end{enumerate}

We now explain the rationale behind those optimizations. Let $G_s(V_s,E_s)$ be an induced subgraph of $G_1$.

\begin{itemize}
    \item For (1), if component $G_1$ is simple, in any induced subgraph $G_s(V_s,E_s)$ from $G$, separating a node $v$ from $G_s$ requires to remove at most $|V_s|-1$ edges. (Here, $ |V_s|-1 \leq |V_1|-1 < k$, because $G_1$ is simple and $|V_1| \leq k$.) In other words, there exists a cut $E_{cut}$ for $G_s$ with $|E_{cut}| < k$. As a result, $\kappa(G_s) < k$. There is no induced $k$-edge-connected subgraph from $G_1$.
    \item As to (2), in any induced subgraph $G_s(V_s,E_s)$, separating a node $v$ from $G_s$ requires to remove at most $\Delta(G_1)$ edges. Since $\Delta(G_1) < k$, we have $\kappa(G_s) < k$ for a similar reason as (1). Note that (2) also holds for multiple graphs, if $G_1$ is a simple graph, (1) is a special case of (2).
    \item For (3), the rationale is obvious, removing $v$ is a special light-weighted cut.
    \item Finally, (4) is supported by Theorem 1 in~\cite{1966}. We rephrase the theorem as Lemma~\ref{lemm:1966} for easy reference. According to Lemma~\ref{lemm:1966} and $\delta(G_1) \geq k$, we know $G_1$ is $k$-edge-connected if the conditions in (4) are satisfied.
\end{itemize}


\begin{lemma}
Let $\delta(G)$ be minimum degree among all vertices in $G(V,E)$, if $\delta(G) \geq \left\lfloor |V|/2 \right\rfloor $, then $\kappa(G) = \delta(G)$.
\label{lemm:1966}
\end{lemma}

All the above four optimizations are designed to avoid performing the min-cut algorithm in line 3 in Algorithm~\ref{algo:basic}. Condition checks (e.g., checking $|V_1| \leq k$, $\Delta(G_1) < k$ ) and variable maintenance (e.g., updating $|V_1|$, $\Delta(G_1)$, $\delta(G_1)$, $deg(v)$) can be done together in $O(|V|+|E|)$ time, more efficient than the SW min-cut algorithm at $O(|E||V| + |V|^2 \log |V|)$.

ktrussMaintain.bbl
\begin{thebibliography}{10}

\bibitem{DBLP:journals/web/truss}
Jonathan Cohen.
\newblock Trusses: Cohesive subgraphs for social network analysis.
\newblock 2008.

\bibitem{DBLP:journals/ijcsa/MeyerBOS11}
Manfred Meyer, Markus Balsam, Arlo O'Keeffe, and Christian Schl{\"u}ter.
\newblock Admotional: Towards personalized online ads.
\newblock {\em IJCSA}, 8(2):59--80, 2011.

\bibitem{RePEc:ucp:jconrs:v:14:y:1987:i:3:p:350-62}
Jacqueline~Johnson Brown and Peter~H Reingen.
\newblock Social ties and word-of-mouth referral behavior.
\newblock {\em Journal of Consumer Research: An Interdisciplinary Quarterly},
  14(3):350--62, December 1987.

\bibitem{LinkedIn}
Leena Rao.
\newblock Linkedin now adding two new members every second.
\newblock {\em TechCrouch.com}, Aug 2011.

\bibitem{RePEc:spr:psycho:v:14:y:1949:i:2:p:95-116}
R.~Luce and Albert Perry.
\newblock A method of matrix analysis of group structure.
\newblock {\em Psychometrika}, 14(2):95--116, 1949.

\bibitem{DBLP:conf/latin/AbelloRS02}
James Abello, Mauricio G.~C. Resende, and Sandra Sudarsky.
\newblock Massive quasi-clique detection.
\newblock In {\em LATIN}, pages 598--612, 2002.

\bibitem{DBLP:journals/tods/ZengWZK07}
Zhiping Zeng, Jianyong Wang, Lizhu Zhou, and George Karypis.
\newblock Out-of-core coherent closed quasi-clique mining from large dense
  graph databases.
\newblock {\em ACM Trans. Database Syst.}, 32(2):13, 2007.

\bibitem{n_clique}
R.~Luce.
\newblock Connectivity and generalized cliques in sociometric group structure.
\newblock {\em Psychometrika}, 15(2):169--190, 1950.

\bibitem{n_clan}
Robert Mokken.
\newblock Cliques, clubs and clans.
\newblock {\em Quality \& Quantity: International Journal of Methodology},
  13(2):161--173, 1979.

\bibitem{Seidman1978}
Stephen~B. Seidman.
\newblock A graph-theoretic generalization of the clique concept.
\newblock {\em Journal of Mathematical Sociology}, 6:139 -- 154, 1978.

\bibitem{Seidman1983269}
Stephen~B. Seidman.
\newblock Network structure and minimum degree.
\newblock {\em Social Networks}, 5(3):269 -- 287, 1983.

\bibitem{DBLP:conf/edbt/ZhouLYLCL12}
Rui Zhou, Chengfei Liu, Jeffrey~Xu Yu, Weifa Liang, Baichen Chen, and Jianxin
  Li.
\newblock Finding maximal k-edge-connected subgraphs from a large graph.
\newblock In {\em EDBT}, pages 480--491, 2012.

\bibitem{DBLP:journals/corr/cs-DS-0207078}
Andr{\'a}s~A. Bencz{\'u}r and David~R. Karger.
\newblock Randomized approximation schemes for cuts and flows in capacitated
  graphs.
\newblock {\em CoRR}, cs.DS/0207078, 2002.

\bibitem{DBLP:journals/tpds/LiangBS01}
Weifa Liang, Richard~P. Brent, and Hong Shen.
\newblock Fully dynamic maintenance of k-connectivity in parallel.
\newblock {\em IEEE Trans. Parallel Distrib. Syst.}, 12(8):846--864, 2001.

\bibitem{Wang:2012:TDM:2311906.2311909}
Jia Wang and James Cheng.
\newblock Truss decomposition in massive networks.
\newblock {\em Proc. VLDB Endow.}, 5(9):812--823, May 2012.

\bibitem{DBLP:conf/semweb/RichardsonAD03}
Matthew Richardson, Rakesh Agrawal, and Pedro Domingos.
\newblock Trust management for the semantic web.
\newblock In {\em International Semantic Web Conference}, pages 351--368, 2003.

\bibitem{DBLP:journals/corr/abs-0810-1355}
Jure Leskovec, Kevin~J. Lang, Anirban Dasgupta, and Michael~W. Mahoney.
\newblock Community structure in large networks: Natural cluster sizes and the
  absence of large well-defined clusters.
\newblock {\em CoRR}, abs/0810.1355, 2008.

\bibitem{Cohen:2009:GTM:1591877.1592018}
Jonathan Cohen.
\newblock Graph twiddling in a mapreduce world.
\newblock {\em Computing in Science and Engg.}, 11(4):29--41, July 2009.

\bibitem{DBLP:journals/pvldb/ZhaoT12}
Feng Zhao and Anthony K.~H. Tung.
\newblock Large scale cohesive subgraphs discovery for social network visual
  analysis.
\newblock {\em PVLDB}, 6(2):85--96, 2012.

\bibitem{DBLP:journals/corr/abs-1207-4567}
Rong-Hua Li and Jeffrey~Xu Yu.
\newblock Efficient core maintenance in large dynamic graphs.
\newblock {\em CoRR}, abs/1207.4567, 2012.

\bibitem{newman-2004-69}
M.~E.~J. Newman and M.~Girvan.
\newblock Finding and evaluating community structure in networks.
\newblock {\em Physical Review E}, 69:026113, 2004.

\bibitem{DBLP:journals/pami/ShiM00}
Jianbo Shi and Jitendra Malik.
\newblock Normalized cuts and image segmentation.
\newblock {\em IEEE Trans. Pattern Anal. Mach. Intell.}, 22(8):888--905, 2000.

\bibitem{DBLP:conf/kdd/ZhangWWZ09}
Yuzhou Zhang, Jianyong Wang, Yi~Wang, and Lizhu Zhou.
\newblock Parallel community detection on large networks with propinquity
  dynamics.
\newblock In {\em KDD}, pages 997--1006, 2009.

\bibitem{DBLP:conf/kdd/XuYFS07}
Xiaowei Xu, Nurcan Yuruk, Zhidan Feng, and Thomas A.~J. Schweiger.
\newblock Scan: a structural clustering algorithm for networks.
\newblock In {\em KDD}, pages 824--833, 2007.

\bibitem{DBLP:conf/kdd/SatuluriP09}
Venu Satuluri and Srinivasan Parthasarathy.
\newblock Scalable graph clustering using stochastic flows: applications to
  community discovery.
\newblock In {\em KDD}, pages 737--746, 2009.

\bibitem{DBLP:journals/jgaa/PonsL06}
Pascal Pons and Matthieu Latapy.
\newblock Computing communities in large networks using random walks.
\newblock {\em J. Graph Algorithms Appl.}, 10(2):191--218, 2006.

\end{thebibliography}
