# Outlier Detection and Prediction in Evolving Communities
## 4 COTILES for Outlier Detection
### Extending Cottles  
We extend Cottles to evaluate the nodes' outlier scores while at the same time performing community detection. The algorithm receives a streaming source of temporally labeled edges as input, then performs clustering, leading to community detection, while the Label Set Match of each node computed in tandem with the Community Focus derived from the extracted communities leads to an outlier score for each node. At the end of each observation window, the current state of the community and outliers structure is extracted. Based on this, outliers are detected and assumptions can be made about the nodes that are most likely to play a secondary role in the network in the future. \begin{table}
\begin{tabular}{l l l} \hline \(L_{(u,v)}\) & Edge labelset & Labels of edge \((u,v)\) \\ \(L_{u}\) & Node labelset & Labels of node \(u\), inherited by the edges it takes part \\ \(L_{C}\) & Community labelset & Labels describing the contents of community \(C\) at a time \\ \(a\) & alpha weight & Leverage between structure and content during community detection \\ \(w\) & we weight & Leverage between structure and content during outlier detection \\ \(OS_{u}\) & Node outlier score & Outlier score of node \(u\) \\ \(thres_{OS}\) & Outlier score threshold & Threshold for a node to be assigned as outlier \\ \hline \end{tabular}
\end{table} 
Table 3: Symbols used. Algorithm 1 details the extended COTILES procedure. Initially, it starts the observation window time and extracts the labels from the network's attributes (lines 1-2). Then, the algorithm retrieves the next interaction of the graph, \((u,v)\), consisting of two end nodes \(u\) and \(v\), its set of labels \(L_{u,v}\), and its timestamp \(t_{k}\) (line 3). The timestamps of both edges and labels are updated or initialized based on whether or not these edges or labels already exist in the graph (line 4). In parallel, expired labels and edges are removed from the graph (line 5). Immediately afterwards, every new edge retrieved from the stream is added to the graph if it was not already part of it (line 7). Proceeding to the main functionality of COTILES for outlier detection in evolving communities, we distinguish four cases based on the neighborhoods of the two nodes \(u\) and \(v\), where we denote the set of neighbors of \(u\) as \(\Gamma(u)\). 1. If the nodes of the new edge have only one neighboring node, this means that they have no other connections, and cannot be members of any community yet; thus, the algorithm does not take any actions in terms of community detection. Only the outlier scores of the nodes are computed (lines 8-11). These outlier scores will be high as concerns their structure, as Community Focus is 0, although their Label Set Match could balance their outlierness. 2. Next, the algorithm checks whether each of nodes \(u\) and \(v\) belong to any community core (lines 12-13). Because peripheral nodes are not allowed to propagate community membership, no action is performed if neither node is core (line 14). 3. If one of the nodes is a core node of a community with a neighborhood greater than 0 and the other node is appearing for the first time, then the core node spreads its community membership to its neighbors through peripheral propagation, which includes checking the constraint for content similarity before adding a node to a community. At the same time, the outlier score of this node and its neighborhood is re-evaluated, as the updating of the community structure affects all of them (lines 16-25). 4. The final case is when both nodes \(u\) and \(v\) are existing core nodes in \(G\) (lines 26-46). Then, the common neighbors of the two core nodes are computed (line 27); based on this, two more scenarios are possible: 1. If nodes \(u\) and \(v\) do not have common neighbors, peripheral propagation takes place, as in the previous case (lines 28-30). 2. If \(u\) and \(v\) have common neighbors, core propagation takes place.