# Large Scale Community Detection Using a Small World Model
## 5 Proposed Methodology  
Detecting communities in a social network having a good number of nodes in a reasonable amount of time is a challenging task due to its size and structure. In this work, distributing computing environment has been considered for processing large-scale networks. Hadoop is a framework applied to solving the complex problem by distributing the computation in multiple nodes in the cluster. Hadoop implicitly schedules the pieces of task on the different computing node. It automatically takes care of load balancing and resource scheduling over the cluster of nodes. Users need not worry about the internal execution policy. However, users can provide the application specific mapper and reducer program to the Hadoop framework. Users have the control over the Map-Reduce program structure but does not have control over execution environment. In this work, the community detection process in Hadoop has been carried out in the following two phases:  
* [noitemsep,topsep=0 pt]
* mapper phase,
* reducer phase. Prior to the computation in Hadoop, the random walk process has been carried out in order to visit all the nodes in the network. In this work, similarity values between all pair of nodes have first been calculated from the transition probability matrix. Transition matrix has been generated separately for random walk lengths 1 to 3. In the mapper phase, community memberships of nodes are being evaluated by using the local information available at each node. In a Small world network model, quick navigation is possible through two fundamental processes: one is to find the short chain of acquittance and the other is to use only local information regarding structure around the node. The community detection process starts from a randomly selected source node. Neighboring nodes who have similarity value less than the threshold value, \(\eta\), are identified and then included in the same community, to which the source node belongs. Here, \(\eta\) is treated as the clustering parameter for a small world model that determines the probability of having a connection between two nodes in the network. Small world model parameters have been determined based on the random walk in the network. Once a node has been mapped with a community number, the node is temporarily deleted from the graph in order to reduce the computation. For the sake of simplicity, the undirected graph has been taken into consideration. It is observed that a real world social network follows a small world network, or, in other words, by following a small number of steps, one can visit all other nodes in the network. Mapper phase nodes are mapped into their community in the order of their reachability from the source node. Steps adopted in the mapper phase are shown in Algorithm 1. The execution flow for community detection is presented in Figure 1.  
```
Mapper (Source Node, Community Membership, Graph G) Input : The social network graph in the form of edge lists. Output : Community Membership for each node in the form of (Key,Value) pair. Here Community Membership is the Key and (Walk Length (WL), Node ID) is the Value. Initialization : Select a node randomly as the Source Node. C_append (Source Node) C = NULL WL=0, Community Membership=1 Emit(Community Membership, WL, Source Node, NULL)
1. for WL=1 to 3
2. for all \(v\) in C
3. for each neighbor \(\
ot\in C^{{}^{\prime}}\) and Sim(Node \(v\), Neighbor Node) \(\leq\)\(\eta\)
4. emit (Community Membership, WL, Neighbour Node)
5. endfor
6. Delete \(v\) from both Graph and \(C\)
7. endfor
8.\(C=C\)
9. Delete the nodes in \(C^{{}^{\prime}}\), because they are already visited. 10. end for
11. Community Membership++
12. Source Node = Random source node for next community
13. if graph is empty
14. exit()
15. else
16. Mapper(Source Node, Community Membership, Graph)
17. endif
```  
**Algorithm 1**Community detection using small world phenomenon (CDSW). Figure 1: Execution flow for community detection using small world phenomenon.