Algorithms and dynamical models for communities and reputation in social networks

Social networks have become increasingly more available the past decade, mainly because of huge online social networks such as facebook and twitter. Understanding how these networks are organised and how they function tells us something about how humans connect to each other. One of the most prominent feature of most social networks is that people tend to form groups. People within such groups tend to know one another. Each group then has relatively many links within the group and few links outside the group. It is not straightforward how to detect such groups—usually termed communities—in social networks. In this thesis we review various methods for community detection. One of the most well-known methods is that of modularity, which has various deficits, the most important one being the so-called resolution limit. We address these shortcomings by proposing a novel method we call the Constant Potts Model (CPM). We prove that it doesn't suffer from the resolution limit. In addition, we introduce a measure of the significance of a partition, based on asymptotic subgraph probabilities. This measure can be used to establish whether such a partition may occur by chance in a random graph, or whether that is very unlikely. Usually, when people talk about social networks, it is tacitly assumed we are talking about friends. Yet not all links have a positive connotation, and we might imagine also having negative links, such as conflict, war or hatred. We briefly consider how to incorporate such negative links in community detection methods. In addition, we investigate the potential dynamics of such negative links inspired by a sociological theory known as social balance. Finally, we suggest a method for using negative links to establish some reputation of the nodes of the network.