Evolutionary Role Mining in Complex Networks by Ensemble Clustering

Sarvenaz Choobdar, Pedro Ribeiro and Fernando Silva

2017

Abstract

The structural patterns in the neighborhood of nodes assign unique roles to the nodes. Mining the set of existing roles in a network provides a descriptive profile of the network and draws its general picture. This paper proposes a new method to determine structural roles in a dynamic network based on the current position of nodes and their historic behavior. We develop a temporal ensemble clustering technique to dynamically find groups of nodes, holding similar tempo-structural roles. We compare two weighting functions, based on age and distribution of data, to incorporate temporal behavior of nodes in the role discovery. To evaluate the performance of the proposed method, we assess the result s from two points of view: 1) goodness of fit to current structure of the network; 2) consistency with historic data. We conduct the evaluation using different ensemble clustering techniques. The results on real world networks demonstrate that our method can detect tempo-structural roles that simultaneously depict the topology of a network and reflect its dynamics with high accuracy.

Keywords

Graph mining; complex networks; structural role mining; evolutionary clustering; ensemble clustering

Reference (text)

Sarvenaz Choobdar, Pedro Ribeiro and Fernando Silva. Evolutionary Role Mining in Complex Networks by Ensemble Clustering. Proceedings of the 32nd ACM Symposium On Applied Computing - Social Network and Media Analysis Track (ACMSAC), pp. 1053-1060, ACM, Marrakech, Morocco, April, 2017.

Bibtex

@inproceedings{ribeiro-ACMSAC2017-SONAMA,
  author = {Sarvenaz Choobdar and  Pedro Ribeiro and Fernando Silva},
  title = {Evolutionary Role Mining in Complex Networks by Ensemble Clustering},
  doi = {10.1145/3019612.3019815},
  booktitle = {32nd ACM Symposium On Applied Computing - Social Network and Media Analysis Track},
  pages = {1053-1060},
  publisher = {ACM},
  month = {April},
  year = {2017}
}