A combinatorial approach to role discovery

Albert Arockiasamy, Aristides Gionis, Nikolaj Tatti

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

3 Citations (Scopus)


We provide a new formulation for the problem of role discovery in graphs. Our definition is structural: Two vertices should be assigned to the same role if the roles of their neighbors, when viewed as multi-sets, are similar enough. An attractive characteristic of our approach is that it is based on optimizing a well-defined objective function, and thus, contrary to previous approaches, the role-discovery task can be studied with the tools of combinatorial optimization. We demonstrate that, when fixing the number of roles to be used, the proposed role-discovery problem is NP-hard, while another (seemingly easier) version of the problem is NP-hard to approximate. On the positive side, despite the recursive nature of our objective function, we can show that finding a perfect (zero-cost) role assignment with the minimum number of roles can be solved in polynomial time. We do this by connecting the zero-cost role assignment with the notion of equitable partition. For the more practical version of the problem with fixed number of roles we present two natural heuristic methods, and discuss how to make them scalable in large graphs.

Original languageEnglish
Title of host publicationProceedings - 16th IEEE International Conference on Data Mining, ICDM 2016
Number of pages6
ISBN (Electronic)9781509054725
Publication statusPublished - 31 Jan 2017
MoE publication typeA4 Article in a conference publication
EventIEEE International Conference on Data Mining - Barcelona, Spain
Duration: 12 Dec 201615 Dec 2016
Conference number: 16

Publication series

NameIEEE International Conference on Data Mining
ISSN (Print)1550-4786


ConferenceIEEE International Conference on Data Mining
Abbreviated titleICDM


Dive into the research topics of 'A combinatorial approach to role discovery'. Together they form a unique fingerprint.

Cite this