Finding Dominant Nodes Using Graphlets David Aparício, Pedro Ribeiro, Fernando Silva and Jorge Silva 2019

Abstract

Finding important nodes is a classic task in network science. Nodes are important depending on the context; e.g., they can be (i) nodes that, when removed, cause the network to collapse or (ii) influential spreaders (e.g., of information, or of diseases). Typically, central nodes are assumed to be important, and numerous network centrality measures have been proposed such as the degree centrality, the betweenness centrality, and the subgraph centrality. However, centrality measures are not tailored to capture one particular kind of important nodes: dominant nodes. We define dominant nodes as nodes that dominate many others and are not dominated by many others. We then propose a general graphlet-based measure of node dominance called graphlet-dominance (GD). We analyze how GD differs from traditional network centrality measures. We also study how certain parameters (namely the importance of dominating versus not being dominated and indirect versus direct dominances) influence GD. Finally, we apply GD to author ranking and verify that GD is superior to PageRank in four of the five citation networks tested.

Keywords

Graphlets; Node centrality; Node dominance; PageRank

Digital Object Identifier (DOI)

doi 10.1007/978-3-030-36687-2_7

Journal/Conference/Book

8th International Conference on Complex Networks and their Applications

Reference (text)

David Aparício, Pedro Ribeiro, Fernando Silva and Jorge Silva. Finding Dominant Nodes Using Graphlets. Proceedings of the 8th International Conference on Complex Networks and their Applications (CNA), pp. 77-89, Springer, Lisbon, Portugal, December, 2019.

Bibtex

@inproceedings{ribeiro-CNA2019,
  author = {David Aparício and  Pedro Ribeiro and  Fernando Silva and Jorge Silva},
  title = {Finding Dominant Nodes Using Graphlets},
  doi = {10.1007/978-3-030-36687-2_7},
  booktitle = {8th International Conference on Complex Networks and their Applications},
  pages = {77-89},
  publisher = {Springer},
  month = {December},
  year = {2019}
}