Related work

We are using community detection algorithms to analyze a PPI network in this project. There is a large body of work on community detection. in this section, we only discuss the most related works.

Community detection

Communities in a network are the groups of nodes, which are highly connected to each other than to the rest of the nodes in the network [3]. There are various community detection techniques.

Graph partitioning can be considered as a traditional community detection technique. It partition a graph into K clusters of predefined size such that the edges between these clusters are minimized. Well-known example of graph partitions are Multi-level partitioning and spectral graph partitioning.

Hierarchical clustering is used when the graphs may contain hierarchical structure, that is each community may be a collection of small clusters at different levels. In such cases, hierarchical clustering techniques may be used to identify the multilevel community structure of the graph. Hierarchical clustering techniques are based on the vertex similarity measure.

The Random Walk is adopted to identify communities. In a random walk, the walker starts to walk inside a community from a node and it moves to the neighboring node selected randomly and uniformly. Heuristic embedding techniques known as node2Vec or DeepWalk are currently receiving a lot of attention in the machine learning community [4], [5]. These techniques are based on random walks.