Discovering dynamic communities in interaction networks

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en
dc.contributor.advisor Gionis, Aristides
dc.contributor.advisor Tatti, Nikolaj
dc.contributor.author Rozenshtein, Polina
dc.date.accessioned 2014-08-29T06:59:36Z
dc.date.available 2014-08-29T06:59:36Z
dc.date.issued 2014-08-21
dc.identifier.uri https://aaltodoc.aalto.fi/handle/123456789/13903
dc.description.abstract Very often online social networks are defined by aggregating information regarding the interaction between the nodes of the network. For example, a call graph is defined by considering an edge for each pair of individuals who have called each other at least once --- or at least k times. Similarly, an implicit social network in a social-media site is defined by considering an edge for each pair of users who have interacted in some way, e.g., have made a conversation, commented to each other's content, etc. Despite the fact that this type of definitions have been used to obtain a lot of insights regarding the structure of social networks, it is obvious that they suffer from a severe limitation: they neglect the precise time that the interaction between network nodes occurs. In this thesis we propose to study interaction networks, where one considers not only the underlying topology of the social network, but also the exact time instances that nodes interact. In an interaction network an edge is associated with a time stamp, and multiple edges may occur for the same pair of nodes. Consequently, interaction networks offer a more fine-grained representation that can be used to reveal otherwise hidden dynamic phenomena in the network. In the context of interaction networks, we study the problem of discovering communities, which are dense in terms of the underlying network structure, and whose edges occur in short time intervals. Such communities represent groups of individuals who interact with each other in some specific time instances, for example, a group of employees who work on a project and whose interaction intensifies before certain project milestones. We prove that the problem we define is NP-hard, and we provide effective algorithms by adapting techniques used to find dense subgraphs. We perform extensive evaluation of the proposed methods on synthetic and real datasets, which demonstrates the validity of our concepts and the good performance of our algorithms. en
dc.format.extent 61+3
dc.format.mimetype application/pdf en
dc.language.iso en en
dc.title Discovering dynamic communities in interaction networks en
dc.type G2 Pro gradu, diplomityö en
dc.contributor.school Perustieteiden korkeakoulu fi
dc.subject.keyword community detection en
dc.subject.keyword graph mining en
dc.subject.keyword social-network analysis en
dc.subject.keyword dynamic graphs en
dc.subject.keyword time-evolving networks en
dc.subject.keyword interaction networks en
dc.identifier.urn URN:NBN:fi:aalto-201408292554
dc.programme.major Machine Learning and Data Mining fi
dc.programme.mcode SCI3015 fi
dc.type.ontasot Master's thesis en
dc.type.ontasot Diplomityö fi
dc.contributor.supervisor Gionis, Aristides
dc.programme Master’s Programme in Machine Learning and Data Mining (Macadamia) 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

Browse

My Account