To identify global community structures in networks is a great challenge that requires complete information of graphs, which is infeasible for some large networks, e.g. large social networks. Recently, local algorithms have been proposed to extract communities for social networks in nearly linear time, which only require a small part of the graphs. In local community extraction, the community extracting assignments are only done for a certain subset of vertices, i.e., identifying one community at a time. Typically, local community detecting techniques randomly start from a vertex and gradually merge neighboring vertices one-at-a-time by optimizing a measure metric. In this chapter, plenty of popular methods are presented that are designed to obtain a local community for a given graph.
TopIntroduction
Community structure is one of the most relevant features of social networks, and with the growth of interest in the study of social networks, great efforts have been made on the area of community detection.
Popularly, a community is a tightly knit sub-graph in a network, in which the within-group links are stronger or denser than between-group links (Wasserman, 1994). Directly optimizing the density inside or the sparseness outside, a number of algorithms have been proposed (Gibson, 1998; Newman, 2004a; Andersen, 2008a; Sharan, 2009), which work well in special cases. Similarly, several approaches come forth based on the concept of flow (Flake, 2000; Flake, 2002; Khandekar, 2009). Recently, researchers have been focusing on algorithms based on the modularity metric (Newman, 2004b; Neman, 2006).
However, these techniques require information of the whole graphs, which might be problematic for large graphs, as the constraint of running time and memory consumption. To overcome the limitation, local community detecting methods emerged, which only need a small subset of vertices instead of the whole graphs.
In general, local community extraction techniques need a seed vertex to create the initial community structure, and then gradually merge neighboring vertices one-at-a-time by optimizing a fitness function. Computing the desired answer by a clustering algorithm for many applications only requires a small subset of vertices to be clustered instead of the whole graph. The process takes time polynomial in 
(the size of extracted community), which is independent to the size of the whole graph. For these two characteristics, local clustering technique is able to extract community structure of huge scale networks. To extract the entire input graph, we can iteratively run the local method, which may be simultaneously obtained by parallel computation.
In this chapter, we will first define the locality for local clustering. Then some famous fitness functions are illustrated, followed with local clustering algorithms presentation.
TopDefinition Of Locality
In order to distinguish local computation from global computation, we must define what information about an input graph we consider to be locally available. Given a single vertex 
, it is assumed that at least the adjacency list containing the identifiers of vertices in 
are known.
For a wider definition, it also allows direct access from a vertex 
to its second neighbors:
(1)Optionally we can allow knowledge of the degrees of the vertices in 
.