Cores Decomposition of Networks

Title: Cores Decomposition of Networks

Research Question: How can we efficiently determine the cores decomposition of a network?

Methodology: The study proposes an efficient algorithm, called the AnO(m)Algorithm for Cores Decomposition of Networks, to determine the cores decomposition of a network. The algorithm is based on the property that a subgraph with a maximum number of vertices of degree k or more is a k-core. The algorithm works by recursively deleting vertices and lines incident with them of degree less than k, until only vertices of degree k or more remain.

Results: The study demonstrates that the proposed algorithm is efficient, with a time complexity of O(m), where m is the number of lines in the network. The algorithm is implemented in a Pascal-like language and is shown to be able to determine the cores decomposition of a network in a practical and efficient manner.

Implications: The development of this algorithm contributes to the field of network analysis by providing an efficient method for determining the cores decomposition of a network. This can be particularly useful in understanding the structure and dynamics of large networks, such as social networks, communication networks, and transportation networks. The algorithm can be applied in various fields, including sociology, computer science, and physics, to analyze and model complex systems.

Link to Article: https://arxiv.org/abs/0310049v1 Authors: arXiv ID: 0310049v1