# Outlier Detection and Prediction in Evolving Communities
## 4 COTILES for Outlier Detection
### Extending Cottles
This algorithm takes as input the corresponding node along with the set of nodes to which it propagates the community periphery. A timestamp \(t_{k}\) indicating the exact execution time is passed along as well. ```
1:\(u\) : node of \(G\), \(nodes\) : a set of nodes, \(t_{k}\) : timestamp. 2:for\(v\in nodes\)do
3:for\(z\in G\).GetCommunityCore\((u)\)do\(\triangleright\)\(\forall\) community core nodes
4:for\(C_{v}\in z\).GetCommunities\(()\)do
5:if\(LabelConstraint(u,v,C_{v},G)==true\)then
6:\(G\).AddToCommunityPeriphery\((v,C_{v})\)
```  
**Algorithm 2** Peripheral Propagation \((u,nodes,t_{k})\)  
Finally, Algorithm 3 refers to the _ComputeOutlierScore_ function is applied within the extended COTILES. It takes a node \(u\) along with its \(w\) weight as inputs. Recall that \(w\in[0,1]\) is a tunable weight allowing significance to be leveraged between content and structure for the calculation of outlier scores. For every active community the Community Focus of the node is computed as the maximum connectivity achieved by the node at the specific time when the function is called (lines 4-6). Specifically, for each community \(C\), _Focus_ is calculated as the fraction of the number of edges of \(u\) with members of \(C\) with respect to the number of all edges of \(u\); its maximum overall community value is selected. Immediately afterwards (lines 7-9), the Label Set Match is computed. The main component of this sub-score referring to content is the maximum _Match_ of the node with respect to the communities, that is, the maximum matching between the content of the node and the content of each community. This calculation is performed in line 7, where the Match of node \(u\) with community \(C\) is the fraction of the number of common labels of \(u\) and \(C\) with respect to the total number of labels included in \(C\). Finally, the outlier score is computed based on the Community Focus and Label Set Match, with the weight parameterized by \(w\) (line 10). Figure 1: High-level flowchart of COTILES for outlier detection. In addition to community detection, the algorithm we propose assigns an outlier score to every active node. The threshold with which nodes can be characterized as inliers or outliers can be set in different context-dependent ways. For instance, we may consider the nodes with scores above the average outlier score to be outliers. The main advantage of our method is the ability to simultaneously detect communities and outliers in an efficient way, as the outlier score is computed for nodes that are affected by each interaction instead of overall. Another advantage is that we measure the outlierness of each node, allowing each node to be directly compared to others. Thus, while two nodes with scores above the average would be outliers, the node with the higher score would be more of an outlier. ```
0: u: node of graph \(G\), w: outlier score weight
0:\(OS_{u}\): Outlier Score of node u
1:\(CommunityFocus_{u}=0\)
2:\(LabelSetMatch_{u}=0\)
3:forC in G.CommunityGdo
4:\(Focus_{u}=\frac{\frac{\alpha\cdot\textit{Mat}Edge(C)}{u\cdot\textit{All} Diffs}}{\textit{if}Focus_{u}>\textit{CommunityFocus}}\)then
5:\(CommunityFocus_{u}\gets Focus_{u}\)\(\triangleright\) Structure Score
6:\(Match_{(u,C)}=\frac{|LabNet_{u}|}{|LabNet_{u}|}\)
7:if\(Match_{(u,C)}>LabelSetMatch_{u}\)then
8:\(LabelSetMatch_{u}\gets Match_{(u,C)}\)\(\triangleright\) Content Score
9:\(OS_{u}\gets 1-[w\cdot CommunityFocus_{u}+(1-w)\cdot LabelSetMatch_{u}]\)\(\triangleright\) Outlier Score
10:return\(OS_{u}\)
```  
**Algorithm 3** Compute Outlier Score \((u,w)\)