We propose the new EI-clustering method for random networks.
Regarding the underlying graph of a random network, EI-clustering
is an advanced statistical tool for community detection and based on the
estimation of the extremal index (EI) associated with each node. The EI
metric is estimated by samples of indices of the node in
uences. The latter
quantities are determined by the PageRank and a Max-Linear Model.
The EI values of both models are estimated by a blocks estimator for
each node which is considered as the root of a Thorny Branching Tree.
Generations of descendant nodes related to the root node of the tree are
used as blocks. The reciprocal of the EI value indicates the average number
of in
uential nodes per generation containing at least one in
uential
node. In the context of random graphs the EI metric indicates the ability
of a randomly selected node to attract highly ranked nodes in its orbit.
Looking at the changing shape of a plot of the EI metric versus the node
number, the node communities are detected. The EI-clustering method
is compared with the conductance measure regarding the data set of a
real Web graph.