Determination the importance of vertices in graph

Abstract

Betweenness is a good measure of the centrality of a vertex in a graph modeling social or communication network. Betweenness centrality is a measure of centrality in a graph based on shortest paths. For every pair of vertices in a connected graph, there exists at least one shortest path between the vertices such that the number of edges that the path passes through is minimized. The betweenness centrality for each vertex is usually defined as the fraction of these shortest paths that pass through the vertex. Therefore, in many models, betweenness is a measure of the influence of a node in the dissemination of information over a network and can also be used to detect communities or cluster in networks. In this paper, we consider betweenness centrality of some Mycielski graphs.