# Outlier Detection and Prediction in Evolving Communities
## 4 COTILES for Outlier Detection
### Extending Cottles
For each common neighbor of the nodes, if it is not a member of any same community, a new community is formed (lines 33-37); otherwise, for each pair of these three nodes, if they are members of the same communities, then they propagate the community membership to the third node (lines 38-46). The outlier score of each node and its neighbors are immediately computed (lines 47-52). At the end, the algorithm checks whether the observation window threshold is reached; if it is, then the detected communities and outliers are returned (lines 53-56). The output consists of the community structure based on returning present communities, their members, and their computed label set and the outlier scores, on which basis the user can set appropriate thresholds to characterize each node as an outlier or not. Further information is extracted, such as merged or split communities, though it is not necessary for outlier detection and can be excluded for efficiency purposes. The flowchart of Figure 1 shows an overall view of the algorithm's steps. ```
0:\(G:\) undirected attributed graph, \(\tau:\) temporal observation window, \(ttl:\) time to live, \(L:\) set of available labels, \(w:\) outlier score weight. 0:\(\mathit{OS}_{w}:\) outlier score of node n
1:\(actual=0\)
2:\(G.extract(L)\)
3:\((u,v,L_{w},t_{k})=\mathit{newInteraction}\)\(\triangleright\) extract textual information (labels) from attributes
4:\(G.UpdateTimestamps()\)
5:\(G.RemoveEprjed\)\(\triangleright\) Remove expired edges and labels from edges and communities. 6:if\((u,v)\
otin G\)then
7:\(G.addEdge((u,v))\)
8:if\(|\Gamma(u)|==1\)and\(|\Gamma(v)|==1\)then
9:\(ComputeOutlierScore(u,w)\)
10:\(ComputeOutlierScore(v,w)\)
11: Continue
12:\(\mathit{core}_{u}=G.GetCommunityCore(u)\)
13:\(\mathit{core}_{u}=G.GetCommunityCore(v)\)
14:if\(\mathit{core}_{u}=\emptyset\)and\(\mathit{core}_{v}==\emptyset\)then
15: Continue
16:if\(|\Gamma(u)|>\emptyset\)and\(|\Gamma(v)|==\emptyset\)then
17:\(G.PeripheralPropagation(u,\{v\},t_{k})\)
18:for\(\Pi(u)>1\)do
19:\(ComputeOutlierScore(i,w)\)
20:\(ComputeOutlierScore(v,w)\)
21:if\(|\Gamma(u)|==\emptyset\)and\(|\Gamma(v)|>\emptyset\)then
22:\(G.PeripheralPropagation(v,\{u\},t_{k})\)
23:for\(\Pi(v)>1\)do
24:\(ComputeOutlierScore(j,w)\)
25:\(ComputeOutlierScore(v,w)\)
26:else
27:\(\mathrm{CN}\)=\(\Gamma(u)\bigcap\Gamma(v)\)\(\triangleright\) CN: Common Neighbors
28:if\(|\Gamma(N]==0\)then
29:\(G.PeripheralPropagation(u,\{v\},t_{k})\)
30:\(G.PeripheralPropagation(v,\{u\},t_{k})\)
31:else
32:for\(z\in\mathrm{CN}\)do\(\triangleright\) Core Propagation
33:if\((u,v,z\
ot\in CommonCommunities)\)then
34:\(G.createCommunity(u,v,z,Labels_{(u,z,z)})\)
35:\(PeripheralPropagation(u,\Gamma(u),t_{k})\)
36:\(PeripheralPropagation(v,\Gamma(v),t_{k})\)
37:\(PeripheralPropagation(z,\Gamma(z),t_{k})\)
38:if\((u.GetCommunities()\cap\mathit{ce}.GetCommunities())>0)\)then
39:\(G.AddToCommunityCore(z,(u\cap v).GetCommunities())\)
40:\(G.PeripheralPropagation(z,\Gamma(z),t_{k})\)
41:if\(((u.GetCommunities()\cap\mathit{zc}.GetCommunities())>0)\)then
42:\(G.AddToCommunityCore(v,(u\cap z).GetCommunities())\)
43:\(G.PeripheralPropagation(\alpha,\Gamma(v),t_{k})\)
44:if\((z.GetCommunities()\cap\mathit{vc}.GetCommunities())>0)\)then
45:\(G.AddToCommunityCore(u,(z\cap v).GetCommunities())\)
46:\(G.PeripheralPropagation(v,\Gamma(u),t_{k})\)
47:for\(\Pi(u)>1\)do
48:\(ComputeOutlierScore(i,w)\)
49:\(ComputeOutlierScore(u,w)\)
50:for\(\Pi\) in \(\Gamma(v)>1\)do
51:\(ComputeOutlierScore(i,w)\)
52:\(ComputeOutlierScore(v,w)\)
53:if\(t-actual\), \(==\tau\)then
54:\(OutputCommunities(G)\)
55:\(OutputOutlierScore(G)\)
56:\(t=actual\),
```  
**Algorithm 1** COTILES for Outlier Detection in Evolving Communities. To provide more insight into the main procedures of community detection in COTILES, we present the algorithm for peripheral propagation (Algorithm 2), which adds nodes to communities' peripheries after validating that their content matches the corresponding community's content.