Hartung-Gorre Verlag
Inh.: Dr. Renate Gorre D-78465 Konstanz Fon: +49 (0)7533 97227 Fax: +49 (0)7533 97228 www.hartung-gorre.de |
S
|
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.
Keywords
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 / D-78465
Konstanz / Germany
Telefon: +49
(0) 7533 97227 Telefax: +49 (0) 7533
97228
http://www.hartung-gorre.de eMail: verlag@hartung-gorre.de