Coreness Variation Rule and Fast Updating Algorithm for Dynamic Networks
Coreness is one of the important indicators to measure the importance of a node. Traditionally, the coreness of a node is measured by <i>k</i>-core decomposition. However, to measure the coreness in a dynamic network, the <i>k</i>-core decomposition method becomes very time-c...
Main Authors: | , , , |
---|---|
Format: | Article |
Language: | English |
Published: |
MDPI AG
2019-04-01
|
Series: | Symmetry |
Subjects: | |
Online Access: | https://www.mdpi.com/2073-8994/11/4/477 |
_version_ | 1811186395850473472 |
---|---|
author | Liang Gao Ge Gao Dandan Ma Lida Xu |
author_facet | Liang Gao Ge Gao Dandan Ma Lida Xu |
author_sort | Liang Gao |
collection | DOAJ |
description | Coreness is one of the important indicators to measure the importance of a node. Traditionally, the coreness of a node is measured by <i>k</i>-core decomposition. However, to measure the coreness in a dynamic network, the <i>k</i>-core decomposition method becomes very time-consuming and inefficient, and cannot meet the need in very large real networks. Recently, the <inline-formula> <math display="inline"> <semantics> <mi mathvariant="script">H</mi> </semantics> </math> </inline-formula> operator method was proposed to calculate the coreness of a node, which provides a novel method to deal with the coreness of a node in a network. In this paper, we decode the coreness variation rule by a symmetric pair of experiments, i.e., deleting and adding edge, on real networks. Then, an algorithm to fast update the coreness of related nodes is proposed. Results on five real networks showed that the performance of the proposed algorithm was greatly enhanced and comprehensively superior to the <i>k</i>-core decomposition algorithm. Our study provides a promising way to optimize the algorithm of coreness calculation in the dynamic networks. |
first_indexed | 2024-04-11T13:45:53Z |
format | Article |
id | doaj.art-10a626b16ba04832ae26c265f4a0f692 |
institution | Directory Open Access Journal |
issn | 2073-8994 |
language | English |
last_indexed | 2024-04-11T13:45:53Z |
publishDate | 2019-04-01 |
publisher | MDPI AG |
record_format | Article |
series | Symmetry |
spelling | doaj.art-10a626b16ba04832ae26c265f4a0f6922022-12-22T04:21:05ZengMDPI AGSymmetry2073-89942019-04-0111447710.3390/sym11040477sym11040477Coreness Variation Rule and Fast Updating Algorithm for Dynamic NetworksLiang Gao0Ge Gao1Dandan Ma2Lida Xu3Key Laboratory of Transport Industry of Big Data Application Technologies for Comprehensive Transport, Beijing Jiaotong University, Beijing 100044, ChinaKey Laboratory of Transport Industry of Big Data Application Technologies for Comprehensive Transport, Beijing Jiaotong University, Beijing 100044, ChinaKey Laboratory of Transport Industry of Big Data Application Technologies for Comprehensive Transport, Beijing Jiaotong University, Beijing 100044, ChinaCollege of Life Science and Technology, Beijing University of Chemical Technology, Beijing 100029, ChinaCoreness is one of the important indicators to measure the importance of a node. Traditionally, the coreness of a node is measured by <i>k</i>-core decomposition. However, to measure the coreness in a dynamic network, the <i>k</i>-core decomposition method becomes very time-consuming and inefficient, and cannot meet the need in very large real networks. Recently, the <inline-formula> <math display="inline"> <semantics> <mi mathvariant="script">H</mi> </semantics> </math> </inline-formula> operator method was proposed to calculate the coreness of a node, which provides a novel method to deal with the coreness of a node in a network. In this paper, we decode the coreness variation rule by a symmetric pair of experiments, i.e., deleting and adding edge, on real networks. Then, an algorithm to fast update the coreness of related nodes is proposed. Results on five real networks showed that the performance of the proposed algorithm was greatly enhanced and comprehensively superior to the <i>k</i>-core decomposition algorithm. Our study provides a promising way to optimize the algorithm of coreness calculation in the dynamic networks.https://www.mdpi.com/2073-8994/11/4/477dynamic networkcorenessℋ operatorcoreness updating algorithm |
spellingShingle | Liang Gao Ge Gao Dandan Ma Lida Xu Coreness Variation Rule and Fast Updating Algorithm for Dynamic Networks Symmetry dynamic network coreness ℋ operator coreness updating algorithm |
title | Coreness Variation Rule and Fast Updating Algorithm for Dynamic Networks |
title_full | Coreness Variation Rule and Fast Updating Algorithm for Dynamic Networks |
title_fullStr | Coreness Variation Rule and Fast Updating Algorithm for Dynamic Networks |
title_full_unstemmed | Coreness Variation Rule and Fast Updating Algorithm for Dynamic Networks |
title_short | Coreness Variation Rule and Fast Updating Algorithm for Dynamic Networks |
title_sort | coreness variation rule and fast updating algorithm for dynamic networks |
topic | dynamic network coreness ℋ operator coreness updating algorithm |
url | https://www.mdpi.com/2073-8994/11/4/477 |
work_keys_str_mv | AT lianggao corenessvariationruleandfastupdatingalgorithmfordynamicnetworks AT gegao corenessvariationruleandfastupdatingalgorithmfordynamicnetworks AT dandanma corenessvariationruleandfastupdatingalgorithmfordynamicnetworks AT lidaxu corenessvariationruleandfastupdatingalgorithmfordynamicnetworks |