A combinatorial approach to role discovery

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en
dc.contributor.advisor Tatti, Nikolaj
dc.contributor.author Arockiasamy, Albert
dc.date.accessioned 2017-02-01T07:43:57Z
dc.date.available 2017-02-01T07:43:57Z
dc.date.issued 2017-01-16
dc.identifier.uri https://aaltodoc.aalto.fi/handle/123456789/24447
dc.description.abstract We provide a new formulation for the problem of role discovery in graphs. Our definition is structural and recursive: 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. en
dc.format.extent 48
dc.format.mimetype application/pdf en
dc.language.iso en en
dc.title A combinatorial approach to role discovery en
dc.type G2 Pro gradu, diplomityö fi
dc.contributor.school Perustieteiden korkeakoulu fi
dc.subject.keyword role detection en
dc.subject.keyword data mining en
dc.subject.keyword graph mining en
dc.subject.keyword social network analysis en
dc.identifier.urn URN:NBN:fi:aalto-201702011416
dc.programme.major Computer Science fi
dc.programme.mcode SCI3042 fi
dc.type.ontasot Master's thesis en
dc.type.ontasot Diplomityö fi
dc.contributor.supervisor Gionis, Aristides
dc.programme Master’s Programme in Computer, Communication and Information Sciences fi

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search archive

Advanced Search

article-iconSubmit a publication


My Account