Hartung-Gorre Verlag

Inh.: Dr. Renate Gorre

D-78465 Konstanz

Fon: +49 (0)7533 97227 Fax: +49 (0)7533 97228
eMail: verlag@hartung-gorre.de





Series in Distributed Computing
edited by Roger Wattenhofer
Vol. 23


Barbara Keller

Society in Graphs

1st edition / 1. Aufl. 2016. XVI, 118 pages/Seiten, € 64,00.

ISBN 978-3-86628-566-8



Individuals are seldom completely independent and should be considered as part of their social surroundings. Their actions both influence their social network and are influenced by the network. This phenomenon can be seen in online social networks formed on online platforms as well as in offline social networks formed, for example, by a group of scholars. In order to understand the fundamental effects of influence in social systems, we model social networks by the means of a well understood mathematical model, a graph.


The first part of this dissertation focuses on the impact of gender on the formation of a network of PhD students and their supervisors. We find evidence for homophilic behavior as well as for the existence of a glass ceiling in a network from the data of co-authorship. From over 1.3 millions of authors of scientific articles in computer science, we extract the student-supervisor relationship graph and analyze its properties.


Furthermore, we introduce mathematical formulations for the occurrence of a glass ceiling and an influence inequality in a network. We establish a network forming process integrating three observed characteristics of this network, namely a smaller entry rate for women, preferential attachment, and homophilic behavior. We prove that these three conditions are sufficient to produce a glass ceiling in the network. We also show, that if one of these three characteristic is missing, the glass ceiling according to the mathematical definition does not occur.


In the second part of this dissertation we examine how opinions evolve in networks. Every node in the network has an initial opinion and the nodes can observe the opinions of their neighbors. We assume a simplistic setting where the nodes are influenced by the opinions of their neighbors and always change their opinion to the opinion of the majority of their neighbors. We study several different variations of this model and investigate how long the system takes to reach a stable state. For asynchronous networks we find unweighted graphs which take a quadratic number of steps until convergence. For unweighted synchronous networks we show graphs with a quadratic convergence, neglecting polylogarithmic factors. Additionally we show that allowing the influence to be weighted increases the convergence time dramatically to exponential time.


About the Author


Barbara Keller received her M.Sc. in 2009 from the Department of Computer Science at ETH Zürich, Switzerland. Her doctoral studies took place from 2010 to 2015 in the Distributed Computing Group at ETH Zürich supervised by Prof. Dr. Roger Wattenhofer. She received her PhD degree from ETH Zürich in November 2015. Her research interests include graph theory, social networks, and distributed computing.




Social Networks, Influence Inequality, Glass Ceiling, Majority Function, Graph Theory, Convergence Time, Network Dynamics.


Series in Distributed Computing in http://www.hartung-gorre.de

Hartung-Gorre Verlag

Hartung-Gorre Verlag / D-78465 Konstanz / Germany

Telefon: +49 (0) 7533 97227  Telefax: +49 (0) 7533 97228
http://www.hartung-gorre.de   eMail: verlag@hartung-gorre.de