Social Networks Research

This work is supported by ISF grant number 1549/13: Structure, Dynamics and Algorithmics of Social Networks: An Axiom- Based Approach (Chen Avin, Zvi Lotker, David Peleg).

On this page... (hide)

Publication


Core-Periphery in Networks: An Axiomatic Approach

  • Authors: Chen Avin, Zvi Lotker, David Peleg, Yvonne Anne Pignolet, Itzik Turkel.
  • Abstract: Recent evidence shows that in many societies worldwide the relative sizes of the economic and social elites are continuously shrinking. Is this a natural social phenomenon? What are the forces that shape this process? We try to address these questions by studying a Core-Periphery social structure composed of a social elite, namely, a relatively small but well-connected and highly influential group of powerful individuals, and the rest of society, the periphery. Herein, we present a novel axiom-based model for the forces governing the mutual influences between the elite and the periphery. Assuming a simple set of axioms, capturing the elite’s dominance, robustness, compactness and density, we are able to draw strong conclusions about the elite-periphery structure. In particular, we show that a balance of powers between elite and periphery and an elite size that is sub-linear in the network size are universal properties of elites in social networks that satisfy our axioms. We note that the latter is in controversy to the common belief that the elite size converges to a linear fraction of society (most recently claimed to be 1%). We accompany these findings with a large scale empirical study on about 100 real-world networks, which supports our results.
  • Publication: under review
  • Files: arXiv version.

Homophily and the Glass Ceiling Effect in Social Networks

  • Authors: Chen Avin, Barbara Keller, Zvi Lotker Claire Mathieu, David Peleg, Yvonne-Anne Pignolet.
  • Abstract: The glass ceiling effect has been defined in a recent US Federal Commission report as “the unseen, yet unbreakable barrier that keeps minorities and women from rising to the upper rungs of the corporate ladder, regardless of their qualifications or achievements”. It is well documented that many societies and organizations exhibit a glass ceiling. In this paper we formally define and study the glass ceiling effect in social networks and propose a natural mathematical model, called the biased preferential attachment model, that partially explains the causes of the glass ceiling effect. This model consists of a network composed of two types of vertices, representing two sub-populations, and accommodates three well known social phenomena: (i) the “rich get richer” mechanism, (ii) a minority-majority partition, and (iii) homophily. We prove that our model exhibits a strong moment glass ceiling effect and that all three conditions are necessary, i.e., removing any one of them will prevent the appearance of a glass ceiling effect. Additionally, we present empirical evidence taken from a mentor-student network of researchers (derived from the DBLP database) that exhibits both a glass ceiling effect and the above three phenomena.
  • Publication: Accepted to ITCS 2015.
  • Files: (currently not available).

Distributed Computing on Core-Periphery Networks: Axiom-based Design

  • Authors: Chen Avin, Michael Borokhovich, Zvi Lotker, David Peleg.
  • Abstract: Inspired by social networks and complex systems, we propose a core-periphery network architecture that supports fast computation for many distributed algorithms and is robust and efficient in number of links. Rather than providing a concrete network model, we take an axiom-based design approach. We provide three intuitive (and independent) algorithmic axioms and prove that any network that satisfies all axioms enjoys an efficient algorithm for a range of tasks (e.g., MST, sparse matrix multiplication, etc.). We also show the minimality of our axiom set: for networks that satisfy any subset of the axioms, the same efficiency cannot be guaranteed for \emph{any} deterministic algorithm.
  • Publication: In Proc. 41st Int. Colloq. on Automata, Languages, and Programming (ICALP) 2014, Part II (2014), pp. 399–410. bib file.
  • Files: arXiv version, Conference version.