# Outlier Detection and Prediction in Evolving Communities
## 3 Background  
A social graph can be modeled as an undirected graph \(G=(V,E)\). Each node \(u\in V\) of the graph corresponds to a user of the social network. Between these nodes, there are edges \((u,v)\in E\) that correspond to interactions between users of the network. To model time evolution, edges in the graph require a timestamp \(t_{(u,v)}\) that represents the time point when the interaction occurs. Furthermore, to incorporate content, graphs are attributed such that for each edge \((u,v)\) we can extract its textual attributes in the form of labels. This results in a labeled set \(L_{(u,v)}\) that corresponds to the content of the interaction, which usually is a set of tags or text exchanged between nodes \(u\) and \(v\). Thus, based on the definition in [38], we have the following definition. **Definition 1** (Temporal-Labeled Graph). : _A temporal-labeled graph on \(G\) is an attributed graph \(G(T)=(V,E,L,T)\) from which the attributes of time and content have been extracted; \(T=\{T_{e}\subseteq\mathbb{N}:e\in E\}\) refers to the set of timestamps of the edges of \(G\), while \(L\) refers to the global set of labels that appear in \(G\)._  
_Community Detection with COTLES_  
The widespread definition referring to communities in social graphs describes them as sub-graphs with higher connectivity between their members than with nodes outside of the community. COTLES [6] is an online community detection algorithm implemented to be applied in temporal-labeled social networks that, in addition to the structural information on which most community detection algorithms focus, takes content into account in order to form more thematically cohesive communities. It additionally considers interaction expiration and supports overlapping communities. The advantages of COTLES are that, in contrast to many other community detection algorithms, it does not require the number of communities to be provided as input; it allows overlapping communities; it is, as mentioned before, online; and it applies an edge aging factor, meaning that edges and labels can be removed from the network if they stay inactive for a predefined period. The algorithm identifies two roles of nodes participating in communities: _core_ and _peripheral_ nodes. A community is formed when at least three nodes have connections  
\begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline  & \multicolumn{2}{c}{**Dimensions**} & \multicolumn{2}{c}{**Outlierness**} & \multicolumn{2}{c}{**Information**} & \multicolumn{2}{c}{**Dynamic**} \\ \hline
**Paper** & **Structure** & **Content** & **Label** & **Degree** & **Local** & **Global** & \begin{tabular}{c} **Snapshot** \\ **-Based** \\ \end{tabular}  & **Online** \\ \hline
[21] & ✓ & & & ✓ & & ✓ & & \\ \hline
[22,23] & ✓ & & & ✓ & ✓ & & \\ \hline
[24] & ✓ & & ✓ & & ✓ & & \\ \hline
[25] & & ✓ & & ✓ & & ✓ & & \\ \hline
[26] & & ✓ & & ✓ & ✓ & & \\ \hline
[27,28] & ✓ & ✓ & ✓ & & & ✓  
between them which are valid in terms of both structure and content. A node is characterized as core if it is involved in at least one triangle with other nodes in the same community. A node is characterized as peripheral if it is a one-hop neighbor of a core node. A community may consist of both of these node categories. Core nodes are the main community representatives that spread community membership during role propagation; this is the main procedure of the algorithm and distributes community membership to nodes based on their neighborhoods. Community membership is propagated by core nodes of each community as they add their neighbors to the community's periphery. Community members turn into core nodes when they form at least one triangle with in-community nodes, and can spread community membership to their new connections by adding them to the community's periphery. The basic characteristic of COTILES is that, in addition to the structural procedure we have described thus far, it exploits the content of the network in the form of labels.