The centrality of Graphs on Different Network Topologies

Analyzing data with visual methods helps us to have a better vision of the complexity of our application. Actually, this scrutinizing helps us to watch the ecosystems of our networks with a better perspective. This evaluation is very helpful for different applications of the network such as clustering, routing of the packets and classification of the network traffic and etc.

For evaluating the performance of our application in the network, we have to find some static and dynamic measures of a given graph for increasing the accuracy and error loss of the packet during the routing among the nodes. Moreover, we can find some essential measures for each graph network such as shortest path, centeredness, closeness and etc. At the advanced level, we can also find some additional measures for each node of networks and some public measures such as diameter and other related measures that are related to the graphs in the networks. For evaluating and analyzing our application we create numbers of graphs with special features(complicated, tree and etc.) and analyze the related measures in that graph. Fig1 is the visualization of the simple graph that the right one corresponds to the star graph and another one is a simple graph with characteristic features.

Each measurement of centrality has its own privilege and makes the importance of social networks so interesting and ubiquitous. In social networks, we are faced with numerous nodes and identities which need to be mined for extracting important information from them. Centrality can be an effective evaluation for analyzing this importance among the millions of nodes. This importance is not only summarized to the number of traffic that is routed to special nodes, but also it can extend the type of the relationships among these nodes and the number of these relations in big networks.

In this article, we will analyze the performance of the nodes in small networks and analyze some centrality measures for some determined topology; Afterwards, I will extend this application to the real-world problem in the last parts. In further parts, we explain the applied centrality in detail. In Experimental Results, we will give a comparison of each network topology and their difference in different conditions.

Fig1. Visualization of a network topology of star and extended star graph

1. Method Description

Centrality: Centrality in graph theory is trying to identify the most important nodes in the graph networks. Due to the high importance of Centrality in different aspects of networks especially social networks, lots of research has been done in this field. In this project, we will utilize some centrality methods in our project which are explained below. As matter of fact, each of these centrality methods has its own definition of centrality and we can not determine one centrality method as the superior one. So we have to analyze and compare them together to find the best centrality metric.

Degree Centrality:

Degree centrality of try to see the centrality of the graph by a number of connections for each vertex. This method analyzes the impact of the nodes with a number of connections in a graph. This method is very suitable when you wanted to find nodes that have a high connection in comparison of other nodes in a network. In other words, this method is suitable for finding very connected individuals, popular individuals, or finding people who routed the high portion of the internet traffic to them. Actually, this centrality method is the simplest method for finding node connectivity.

Eigenvector Centrality

Eigen Centrality measures are very similar to degree centrality in different aspects but it processes an additional step by taking account into how well networks’ nodes are connected and how many links are there between them and counting the number of connections to the nodes with a high degree centrality. Eigen centrality is a good measurement method for finding the social networks, malware propagation systems, and other related systems in the social networks.

Katz Centrality

Katz centrality introduces two positive constants to tackle the problem of eigenvector centrality with zero in-degree nodes. Although this method is introduced as a solution for directed graphs, it can be useful for some applications of undirected graphs as well.

PageRank

PageRank one was figured out by the google research group for ranking the websites in the search engine based on this measurement. This method is effective for understanding citations and authority. PageRank is a variant of EigenCentrality, also assigning nodes a score based on their connections.

Closeness Centrality

This measure scores each node based on their ‘closeness’ to all other nodes within the network. This measure calculates the shortest paths between all nodes, then assigns each node a score based on its sum of shortest paths. For finding the individuals who are best placed to impact the entire network most quickly. Closeness centrality can help find good ‘broadcasters’, but in a highly connected network, you will often find all nodes have a similar score. We can use Closeness to find impact nodes on a single cluster.

Betweenness Centrality

Betweenness centrality measures the number of times a node lies on the shortest path between other nodes. This measure shows which nodes act as ‘bridges’ between nodes in a network. It does this by identifying all the shortest paths and then counting how many times each node falls on one.

Experimental Results

We apply different measures of centrality on different network topologies for showing that each network should be evaluated with its own centrality method. For grasping our work, we apply four types of network topologies. The used topologies are Star graph, Tree, Fully connected, and extended star graph. The visualization of our works is enclosed in Fig1, Fig2, Fig3, and Fig4. Moreover, parametric results are also put in the following tables; Parametric results are also in below each visualization.

As a conclusion we can reach some agreement from this project results that I put below:

• If we want to find very connected individuals, popular people( in social networks), individuals who are likely to hold most among other nodes, degree centrality is suggested.
• If we need to have further processes among the nodes with the policy of degree centrality eigenvalue centrality is suggested(suitable for more complicated networks).
• Hence, all of the centrality measures give effective results for our networks(but each measure gives a different impact for each node in determining the graph).

Fig4.Visualization centrality measures for the fully connected graph.

Conclusion

According to the abovementioned, we can reach an agreement that one centrality method is not comprehensive enough for all of the network topologies. Hence, we need to calculate all of the centrality techniques to find the best one among the state-of-the-art methods. In some topologies, we do not have true results based on the determined results. For an undirected graph, eigenvector centrality is the best decision in most conditions on an undirected graph. Moreover, Katz centrality should be applied in conditions where we have isolated graphs or similar conditions.

References

[1] Newman, Mark. Networks: An Introduction (pp. 168–234, Chapter 7: Measures and Metrics)., Oxford University Press, 2010.