TY - GEN
T1 - Fixed points of graph peeling
AU - Abello, James
AU - Queyroi, François
PY - 2013
Y1 - 2013
N2 - Degree peeling is used to study complex networks. It corresponds to a decomposition of the graph into vertex groups of increasing minimum degree. However, the peeling value of a vertex is non-local in this context since it relies on the connections the vertex has to groups above it. We explore a different way to decompose a network into edge layers such that the local peeling value of the vertices on each layer does not depend on their non-local connections with the other layers. This corresponds to the decomposition of a graph into subgraphs that are invariant with respect to degree peeling, i.e. they are fixed points. We introduce in this context a method to partition the edges of a graph into fixed points of degree peeling, called the iterative-edge-core decomposition. Information from this decomposition is used to formulate a notion of vertex diversity based on Shannon's entropy. We illustrate the usefulness of this decomposition in social network analysis. Our method can be used for community detection and graph visualization.
AB - Degree peeling is used to study complex networks. It corresponds to a decomposition of the graph into vertex groups of increasing minimum degree. However, the peeling value of a vertex is non-local in this context since it relies on the connections the vertex has to groups above it. We explore a different way to decompose a network into edge layers such that the local peeling value of the vertices on each layer does not depend on their non-local connections with the other layers. This corresponds to the decomposition of a graph into subgraphs that are invariant with respect to degree peeling, i.e. they are fixed points. We introduce in this context a method to partition the edges of a graph into fixed points of degree peeling, called the iterative-edge-core decomposition. Information from this decomposition is used to formulate a notion of vertex diversity based on Shannon's entropy. We illustrate the usefulness of this decomposition in social network analysis. Our method can be used for community detection and graph visualization.
UR - http://www.scopus.com/inward/record.url?scp=84893246967&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84893246967&partnerID=8YFLogxK
U2 - 10.1145/2492517.2492543
DO - 10.1145/2492517.2492543
M3 - Conference contribution
AN - SCOPUS:84893246967
SN - 9781450322409
T3 - Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2013
SP - 256
EP - 263
BT - Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2013
PB - Association for Computing Machinery
T2 - 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2013
Y2 - 25 August 2013 through 28 August 2013
ER -