- On the Structure of Fixed Points of Degree Peeling
- Project Year:
2017
- REU Student (s):
Seth Bartynski | University of Pennsylvania
- Student 1 Institution:
University of Pennsylvania
- Project Mentor:
James Abello
- Project Mentor Area:
Computer Science
- Project Abstract:
Degree peeling is frequently used to analyze large
networks. In particular, previous work has focused on using
degree peeling to decompose networks into cohesive subgraphs.
These decompositions allow the researcher to focus in on
particularly important structures within the network at hand.
However, the properties of such structures have not been studied
extensively and may be quite large themselves. Here we examine
the properties of the structures generated by the iterative edge
decomposition of Abello and Queyroi, which are fixed points
of degree peeling. We describe how fixed points of degree peeling
can be combined to form larger fixed points. Furthermore,
we investigate the effects of graph homeomorphism on degree
peeling, which can be very drastic. We provide novel methods for
minimizing this influence. Combined with the edge decomposition
of Abello and Queyroi, our work can be used in network
analysis, community detection, and graph visualization.
