Ranking the Importance of Nodes of Complex Networks by the Equivalence Classes Approach
arXiv:1211.5484
Abstract
Identifying the importance of nodes of complex networks is of interest to the research of Social Networks, Biological Networks etc.. Current researchers have proposed several measures or algorithms, such as betweenness, PageRank and HITS etc., to identify the node importance. However, these measures are based on different aspects of properties of nodes, and often conflict with the others. A reasonable, fair standard is needed for evaluating and comparing these algorithms. This paper develops a framework as the standard for ranking the importance of nodes. Four intuitive rules are suggested to measure the node importance, and the equivalence classes approach is employed to resolve the conflicts and aggregate the results of the rules. To quantitatively compare the algorithms, the performance indicators are also proposed based on a similarity measure. Three widely used real-world networks are used as the test-beds. The experimental results illustrate the feasibility of this framework and show that both algorithms, PageRank and HITS, perform well with bias when dealing with the tested networks. Furthermore, this paper uses the proposed approach to analyze the structure of the Internet, and draws out the kernel of the Internet with dense links.
References in corpus (7)
- Emergence of scaling in random networks
- Cooperative Game Theory Approaches for Network Partitioning
- The structure of scientific collaboration networks
- Identification of influential spreaders in complex networks
- The Rich-Club Phenomenon In The Internet Topology
- Classes of complex networks defined by role-to-role connectivity profiles
- The Complex Network of Evolutionary Computation Authors: an Initial Study