Publication

Abstract : The bridge vertices of an unweighted undirected graph are those vertices whose removal increases the number of connected components of the graph, i.e., the vertices whose removal disconnects the graph. However, not all the bridge vertices are equal. The removal of some of them might end in a single vertex disconnected from the graph, while in other cases, the graph can be split into several small pieces. This paper deals with the latter situation which ultimately finds vertices or articulation points among communities of a graph. A better method to find bridge vertices among a graph with maximal information termination is through maximal cliques and overlapping communities. The proposed method first divides the graph into cliques. These cliques are then merged into communities based on the similarity criteria. Vertices are classified into isolated, overlapping, and bridge vertices. Vertices which can be merged into overlapping communities are merged so that the remaining isolated vertices will form the articulation points or the pure bridge vertices, where removal of such vertices can affect the information passage between communities. After merging, we ignore a situation where removal of a bridge vertex in a graph which ends in a single vertex or a set of vertices which cannot be formed as a community as we focus on community-based vertex classification.