d-central graph model for local cohesive sub graph discovery

Structural cohesion is the sociological concept and it is defined as the minimal number of actors in a social network that needs to be removed to disconnect the group. The extraction of a cohesive subgraph is an important issue in social network analysis and other networks including computer and biological networks. Detecting cohesive subgraph is a graph partitioning problem and is so prominent in network analysis to discover network structure and predicate the behavior of the network components. Existing studies of this problem are classified in implicit and explicit methods. Explicit methods try to find subgraphs with special properties. Most dense subgraphs have overlap and can construct other subgraphs which are common between two dense subgraphs that existing studies cannot find these subgraphs. This paper proposes a new method to address this problem, the proposed method (d-central graph) is able to detect local cohesive subgraphs in weighted or unweighted graphs. We demonstrate a local cohesive subgraph is the largest central subgraph including a central node with a maximum diameter $d$. The proposed explicit method for detecting local cohesive subgraphs tries to detect the largest central subgraph including the central node and its best neighbor which have minimum common neighbors and the min-cut between the central node and its best neighbor can construct two subgraphs with approximately the same number of nodes. The experiments demonstrate the effectiveness of the proposed method in earning high centrality and low diameter compared with other methods on some network graphs. We explain another case study that uses the d-central graph to assign priority to data center network resources.

کلیدواژه ها:

Virtual Networks ، cohesive graph ، local subgraph ، diameter ، network analysis.