# Detection of Hidden Communities in Twitter Discussions of Varying Volumes
## 3 Models and Methods in SNA
### Evaluation Metrics for Community Detection  
In order to evaluate partitions, we decided to use various quality indicators that characterize how similar the structure of connections of a given network is to a community. The metrics are based on the idea that communities are collections of nodes with more connections inside and fewer connections outside. They were selected from a standard set of known metrics, which are commonly used to assess the graph properties of detected communities in a directed graph [30; 31; 32; 33; 34; 35]. Such properties, for example, include the ability to distinguish large communities in a graph, the density of internal connections within formed communities, the number of edges in a graph outside the community, and the ratio of incoming edges to the total number of community edges. In selecting the metrics, we also used the following logic: (1) the metrics must vary in terms of which graph properties they measure; (2) the metrics have to suit both the density-based and pattern-based clustering; and (3) taken together, the metrics must describe the main graph properties in terms of community detection. The metrics selected have no underlying 'ground truth' capacity; that is, none of them can tell whether a hidden community is found or not. However, taken together, the metrics provide for much better clarity on how well the algorithms cluster the graph nodes. The metrics, though, may provide for sociological meaning (e.g., stronger connection of nodes may reveal modularity based on opinion, group belonging, or expression sentiment), but the meaning of the result is task-dependent (e.g., we consider it better when a discussion is less modular, which would mean more equal spread of political opinion). It is not the peculiar sociological meaning that we demand from each metric; taken together, they are to provide for a bigger picture of how close a given algorithm is to finding a closer-to-life number of communities. 1. The _NEDindex_[30] value ranges from 0 to 1. Cluster nodes are more strongly connected to the entire graph if _NEDindex_ tends towards 1, and vice versa, cluster nodes are weakly connected if _NEDindex_ is close to 0. \[D(G)=2\sum_{1\leq i\leq n}e_{i},\]\[NED(C)=\frac{|V_{c}|+|E_{c}|+D(C)}{|V_{c}|+( \begin{array}{cc}|V_{c}|&\\ 2&\end{array} )+D(G,V_{c})},\] \[NEDindex=\sum_{1\leq i\leq n}\frac{NED(C_{i})*D(C_{i})}{D(G)}.\] (2) This metric indicates the strength of the connection between the cluster vertices relative to the entire graph. 2. Directed modularity [31] is an extended version of the modularity metric [32] for directed graphs. The higher the value, the better the result. \[Q=\frac{1}{m}\sum_{ij}\left[A_{ij}-\frac{k_{i}^{in}k_{j}^{out}}{m}\right] \delta_{c_{i}c_{j}}\] (3) Modularity reflects the concentration of edges within communities compared with random distribution of links between all nodes regardless of communities. Modularity also shows the effectiveness of the method to detect large communities. 3. Clustering Coefficient is used in this paper as a version of the clustering coefficient [33] extended for directed and weighted graphs. \[C^{D}=N^{-1}\sum_{i=1}^{N}C_{i}^{D}\] (4) In this metric, the average value of the ratio of existing triangles based on the vertex \(i\) to all kinds of triangles based on this vertex is considered, that is, the completeness of the relationship between the vertices is considered. The closer the metric value is to 1, the better the community detection. 4. Conductance [34] is the proportion of the total number of edges outside the community for unweighted networks or the proportion of the total weight of such edges for weighted networks. This metric allows you to know the \"conductivity\" of the resulting community. The closer the conductance value to 0, the better the quality of the community. \[\frac{\left|E_{c}^{out}\right|}{\left|E_{c}^{in}\right|+\left|E_{c}^{out}\right|}\] (5)
5. Contraction [34] measures the average number of edges per node within community C or the average weight per node of such edges.