In this blog we will discuss the computation of dense sub-graph (community) of sparse graph, which is very common in our real life complex network. We will give introduction about different way of computing sub-graph and finally will spread some light on random walk approach.
Complex network has become important in different domain such as sociology (acquaintance or collaboration networks), biology (metabolic networks, gene networks) or computer science (Internet topology, Web graph, P2P networks). The Graphs of these networks are general globally sparse but locally dense. There exist group of vertices which are highly connected among itself, called communities, but few links to other. This type of structure carries much information about network. One real life example could be our Facebook friends if we draw our friends as node and link between them if they are friend among themselves then we will find a sparse graph having different dense sub graph(community) based on college friend , High school friend , School friend, colleague etc.
Community Computation problem can be related to graph partition problem in which given a graph G = (V,E) with V vertices and E edges, k-way partition of graph is partitioning of graph in k part such that number of edges running over these partitions are minimum. However the algorithm for Graph partition is not well suited for our case, because no of communities and their size is input for Community Computation.
Hierarchical clustering is another classical approach in which nodes are grouped together based on the similarity between nodes, Newman proposed  a greedy algorithm that starts with n communities corresponding to the vertices and merges communities in order to optimize a function called modularity which measures the quality of a partition.
The approach which is discussed here is based on the random walks on a graph  tend to get “trapped” into densely connected parts corresponding to communities. The graph G has its adjacency matrix A: Aij = 1 if vertex i and j are connected and Aij = 0 otherwise. The degree d(i) of the vertex i is the number of its neighbors. A discrete random walk is a process in which a walker is on a vertex and moves to vertex chosen randomly and uniformly among its neighbors. The sequence of visited vertices is a Mrakov chain, the states of which are the vertices of the graph. At each step, the transition probability from vertex i to vertex j is Pij =Aij/d(i). This defines the transition matrix P of random walk. The probability of going from i to j through a random walk of length t is (Pt)ij. It satisfies following two properties of random walk.
Property 1: When length of a path between two vertices i and j tends toward infinity. The probability that a random walker will be at vertex j will totally depend on the degree of vertex j
Property 2: The ratio of probabilities of going from i to j and j to i through a random walk of a fixed length t depend on the degrees d(i) and d(j).
For grouping vertices into communities, we will now introduce a distance r between the vertices that captures the community structure of the graph. This distance will be large if two vertices are in different communities, and on contrary if the distance is small they will be in same community. It will be computed from the information given by the random walk of the graph.
Let us consider a random walk of length t from vertex i to j . t is large enough to gather the topology of graph. However t must not be too long to avoid property 1. The probability Ptij would depend on the degree of the vertices i and j. Each Ptij gives some information about the two vertices i and j, but property 2 says that Ptij and Ptji encode the same information. Finally the information about vertex i is encode inside n probabilities Ptik 1<k<n. Which is nothing but the ith row of matrix Pt. For comparing two vertices we must notice following points.
· If two vertices i and j are in the same community, the probability Ptij will be high be high but if Ptij is high it does not necessarily imply that i and j will be in same community.
· High degree vertex will have always high probability that a random walker will reach there. So Ptij is influenced by the degree d(j) of vetex.
· Two vertices of a same community observe all the other vertices in same way. Thus if i and j are in same community then
Graph Partition Problem
Newman, M.E.J.: Fast algorithm for detecting community structure in networks. Physical Review E 69 (2004) 066133
Computing Communities in Large Networks Using Random Walks - Pascal Pons and Matthieu Latapy