Bilkent University
Department of Computer Engineering


Finding Hidden Hierarchy in Social Networks


Süreyya Emre Kurt
MS Student
(Supervisor: Assoc. Prof. Dr. Buğra Gedik)
Computer Engineering Department
Bilkent University

Stratification among humans is a well-studied concept that significantly impacts how social connections are shaped. Given that on-line social networks capture social connections among people, similar structure exist in these networks with respect to the presence of social hierarchies. In this paper we study the problem of finding hidden hierarchies in social networks, in the form of social levels. The problem is motivated by the need for stratification for social advertising. We formulate the problem into dividing the users of a social network into levels, such that three main metrics are minimized: agony induced by the reverse links in the hierarchy, support disorder resulting from users in higher levels having less impact, and support imbalance resulting from users in the same level having diverse impact. We developed several heuristic algorithms to solve the problem at real-world scales. We present an evaluation that showcases the result quality and running time performance of our algorithms on real-word as well as synthetically generated graphs.


DATE: 27 June, 2016, Monday @ 10:00