Generalized Cores

Title: Generalized Cores

Research Question: Can we develop a more general approach to identifying cores in graphs, based on different properties of vertices?

Methodology: The researchers proposed a new concept called "p-cores," which are based on vertex property functions (p) that can be monotone or non-monotone. Monotone functions are those that have the property "if C1 ⊂ C2, then ∀v ∈ V: p(v, C1) ≤ p(v, C2)." They developed an algorithm to determine p-cores at a given level t.

Results: The researchers showed that for monotone functions, the p-core at level t can be determined by successively deleting vertices with values of p lower than t. They also proved that the result of the algorithm is independent of the order of deletions.

Implications: The generalized cores provide a more flexible and powerful tool for analyzing large graphs and networks. The ability to use different vertex property functions allows for a better understanding of the structure and behavior of these systems. The monotone functions, in particular, offer a simple and efficient way to identify cores, which can be useful in various applications, such as social network analysis, computer science, and physics.

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