Cross-Face Centrality: A New Measure for Identifying Key Nodes in Networks Based on Formal Concept Analysis

Abstract

Discovering influential nodes (or actors) in the network is often the key task of mining, analyzing, and understanding real-life networks. Centrality measures are commonly used to detect important nodes that control the information propagation in the network. While off-the-shelf centrality indices may provide effective node identification in several situations, they frequently produce inadequate results when confronted with massive networks, in the presence of complex local structures or the lack of certain characteristics. In this paper, we introduce Cross-face, a new scalable centrality measurement for the identification of key nodes in such networks. Inspired by the Formal Concept Analysis (FCA) framework, the conceptual idea of “Cross-face” is to leverage the faces of concepts to identify nodes that are located in “face bridges” and have an influential “cross clique” connectivity. Thus, it concurrently measures how the node influences its neighbour nodes through its cross cliques while linking the densely connected substructures of the network via its presence in bridges. Unlike traditional centrality measures, the cross-face of nodes can be computed using only a set of symmetrical concepts, which is often quite small compared to the set of nodes or edges in the network. Our experiments on several real-world networks show the efficiency of Cross-face over existing prominent centrality indices such as betweenness, closeness, eigenvector, and k-shell among others.

Keywords

• Formal concept analysis
• complex networks
• key nodes
• cross-cliques connectivity
• betweenness centrality