Identifying Influential Nodes in Complex Networks Based on Weighted Formal Concept Analysis
Open Access
- 7 March 2017
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Access
- Vol. 5, 3777-3789
- https://doi.org/10.1109/access.2017.2679038
Abstract
The identification of influential nodes is essential to research regarding network attacks, information dissemination, and epidemic spreading. Thus, techniques for identifying influential nodes in complex networks have been the subject of increasing attention. During recent decades, many methods have been proposed from various viewpoints, each with its own advantages and disadvantages. In this paper, an efficient algorithm is proposed for identifying influential nodes, using weighted formal concept analysis (WFCA), which is a typical computational intelligence technique. We call this a WFCA-based influential nodes identification algorithm. The basic idea is to quantify the importance of nodes via WFCA. Specifically, this model converts the binary relationships between nodes in a given network into a knowledge hierarchy, and employs WFCA to aggregate the nodes in terms of their attributes. The more nodes aggregated, the more important each attribute becomes. WFCA not only works on undirected or directed networks, but is also applicable to attributed networks. To evaluate the performance of WFCA, we employ the SIR model to examine the spreading efficiency of each node, and compare the WFCA algorithm with PageRank, HITS, K-shell, H-index, eigenvector centrality, closeness centrality, and betweenness centrality on several real-world networks. Extensive experiments demonstrate that the WFCA algorithm ranks nodes effectively, and outperforms several state-of-the-art algorithms.Keywords
Funding Information
- National Natural Science Foundation of China (61403062)
- Science-Technology Foundation for Young Scientist of SiChuan Province (2016JQ0007)
- Natural Science Foundation of Fujian Province of China (2015J01271)
- Education Hall of Young Teachers’ Scientific Research Project of Fujian Province of China (JAT160469)
This publication has 44 references indexed in Scilit:
- Identifying Influential Nodes in Large-Scale Directed Networks: The Role of ClusteringPLOS ONE, 2013
- Reprint of: The anatomy of a large-scale hypertextual web search engineComputer Networks, 2012
- Leaders in Social Networks, the Delicious CasePLOS ONE, 2011
- Identification of influential spreaders in complex networksNature Physics, 2010
- An incremental algorithm to construct a lattice of set intersectionsScience of Computer Programming, 2009
- Identifying gene-disease associations using centrality on a literature mined gene-interaction networkBioinformatics, 2008
- Ontology-based concept similarity in Formal Concept AnalysisInformation Sciences, 2006
- Authoritative sources in a hyperlinked environmentJournal of the ACM, 1999
- The Mathematics of Infection: Infectious Diseases of Humans . Dynamics and Control. Roy M. Anderson and Robert M. May. Oxford University Press, New York, 1991. viii, 757 pp., illus. $115.Science, 1991
- A NEW MEASURE OF RANK CORRELATIONBiometrika, 1938