# Proactive Caching at the Edge Leveraging Influential User Detection in Cellular D2D Networks
## 4 Proposed Methodology
### Cluster Formation in a Social Network  
The first step of our proposed approach is to detect the cluster of each user in the social network as discussed in the previous subsection. For a given graph \(G=(V,E)\), there exist partitions  
Figure 3: Users’ degree distribution of a generated synthetic network. Figure 2: Synthetic network consisting of 256 users generated using the Barabasi Albert Model. \(C=\{c_{1},c_{2},...c_{k}\}\) of V, where \(|c_{i}|>0\). Our goal is to identify a set of clusters that are densely intra-connected and sparsely interconnected. The process of identifying clusters in social networks is known as community detection. Various kinds of community detection algorithms have been proposed. In this paper, we use the CC-GA algorithm [18]. The main reason for using CC-GA is its promising results when compared to other state-of-the-art algorithms such as the information theoretic algorithm (Infomap) [38] and the label prorogation algorithm (LPA) [39] on various kinds of networks including power-law and Forest fire models. This algorithm uses a well-known SNA measure called a Clustering Coefficient (CC) for generating an initial population. CC gives a better population for a genetic algorithm and results in better clustering of the network. Additionally, the algorithm using CC has shown that it converges very quickly [18]. In the following equation, \(C_{v_{i}}\) represents the value of clustering coefficient of node \(v_{i}\):  
\[C_{v_{i}}=\frac{2L_{v_{i}}}{k_{v_{i}}(k_{v_{i}}-1)}, \tag{5}\]  
where \(L_{v_{i}}\) represents the total number of links between the \(k_{v_{i}}\) neighbors. The higher value of \(C_{v_{i}}\) represents the dense neighborhood of a node. The main intuition behind using CC is that if the neighborhood of a node is densely populated, then it is more likely that all of the neighborhood nodes belong to the same cluster. Furthermore, CC-GA uses Modularity measure [40] as an objective function that is a quality index for clustering of social networks. It can be formally defined as follows:  
\[Q=\sum_{C\in c}\left[\frac{|E(C)|}{m}-\left(\frac{|E(C)|+\sum_{C^{\prime}\in c }|E(C,C^{\prime})|}{|2m|}\right)^{2}\right], \tag{6}\]  
where \(|E(C)|\) represents the number internal links within the cluster while \(E(C,C^{\prime})\) represents the links between clusters. \(m\) represents the total number of links in the whole network. Equation (6) can be rewritten into a precise mathematical formulation as given below:  
\[Q=\sum_{C\in c}\left[\frac{|E(C)|}{m}-\left(\frac{\sum_{o\in c} deg(v)}{|2m|}\right)^{2}\right]. \tag{7}\]  
In Equation (7), the first fraction represents the true intra-connectivity of the users, while the second fraction represents the expected number of links within the cluster. The value of modularity ranges between \(-1\) and \(1\). Greater value of modularity indicates better clustering of the network while a negative value represents an absence of true clustering in the network. CC-GA tries to maximize the value of modularity in order to get nearly optimal clustering of the network. It is to be noted that modularity optimization is an NP-hard problem, which can not be solved with a guaranteed optimal solution. Algorithm 1 presents the pseudocode of CC-GA. Initially, the algorithm requires a graph consisting of vertices (V) and edges (E) as inputs. It also requires a set of input parameters including: the termination criteria (\(r\)), population size (\(P_{n}\)), crossover rate (\(P_{s}\)), mutation rate (\(P_{m}\)), mutation extension rate (\(\alpha\)) and percentage of population (\(T_{c}\)) to be selected for the next iteration. Initially, the algorithm computes CC of all nodes (steps 2-4) and generates the initial population (step 5). Afterwards, the genetic operators (crossover and mutation) are performed iteratively until the termination criterion is satisfied (steps 5-25). The algorithm also uses extension of mutation to merge small communities (step 19), and uses modularity measure as an objective function (steps 9, 15, 21).