Dissertations, Theses, and Capstone Projects

Date of Degree

2-2021

Document Type

Dissertation

Degree Name

Ph.D.

Program

Computer Science

Advisor

Saad Mneimneh

Committee Members

Amotz Bar-Noy

Felisa Vazquez-Abad

Ram Ramanathan

Subject Categories

Numerical Analysis and Computation | Theory and Algorithms

Keywords

network, hypergraph, simplicial complex, preferential attachment, subsumption

Abstract

An affiliation (or two-mode) network is an abstraction commonly used for representing systems with group interactions. It consists of a set of nodes and a set of their groupings called affiliations. We introduce the notion of affiliation network with subsumption, in which no affiliation can be a subset of another. A network with this property can be modeled by an abstract simplicial complex whose facets are the affiliations of the network.

We introduce a new model for generating affiliation networks with and without subsumption (represented as simplicial complexes and hypergraphs, respectively). In this model, at each iteration, a constant number of affiliations is sampled uniformly at random and then nodes are selected from these affiliations with a fixed probability. This results in an implicit preferential attachment growth and a power-law in the degree distribution (where degree is defined as the number of affiliations a node belongs to).

We develop a theoretical model of this network generation procedure, prove that the degree distribution in the hypergraph case is governed by the Yule-Simon distribution, then find the exponent of its power-law tail. Similarly, we show that in the simplicial complex case, the degree distribution also has a power-law tail, and we develop a numerical technique for computing its exponent.

We show that the affiliation size distributions can be concisely described via their generating functions. We develop two numerical techniques for solving the resulting functional equations, find the generating functions and compute their PMFs. Furthermore, we show that at the limit the affiliation size distribution can be approximated by a shifted Poisson or related distribution.

We study the process of a giant component formation in the network, develop a theoretical estimate of the critical threshold for one of the model parameters and compare it with experiments.

For a qualitative analysis of our network generation procedure, we study the average pairwise distance in the network, its assortativity, and clustering coefficient, and use Q-analysis methods to compare our networks with other synthetic networks and real-world networks.

Download

Share

COinS