You are here
Search results
(1  4 of 4)
 Title
 Fairness in Social Network Analysis : Measures and Algorithms
 Creator
 Masrour Shalmani, Farzan
 Date
 2021
 Collection
 Electronic Theses & Dissertations
 Description

The use of machine learning in human subjectrelated tasks has resulted in growing concerns about the inherent biases within such automated decisionmaking algorithms. In response to these concerns, we are witnessing a growing body of literature that focuses on designing fairnessaware machine learning algorithms. However, current fairness research is mostly limited to nonrelational, independent and identicallydistributed (i.i.d) data. To overcome this limitation, this thesis aims to...
Show moreThe use of machine learning in human subjectrelated tasks has resulted in growing concerns about the inherent biases within such automated decisionmaking algorithms. In response to these concerns, we are witnessing a growing body of literature that focuses on designing fairnessaware machine learning algorithms. However, current fairness research is mostly limited to nonrelational, independent and identicallydistributed (i.i.d) data. To overcome this limitation, this thesis aims to develop fairness measures and algorithms for analyzing social networks, which is an important class of relational data. In particular, this work investigates the challenges of ensuring fairness in link prediction, node classification, and network sampling, which are three important network analysis tasks. First, we develop a novel fairnessaware link prediction framework that combines adversarial network representation learning with supervised link prediction based on network modularity measure. We show that this approach promotes more diverse links and addresses the filter bubble problem in social networks. Second, we investigate the node classification problem from a fairness perspective. We introduce a novel yet intuitive measure known as fairness perception and provide an axiomatic approach to analyze its properties. A fairnessaware classification algorithm is developed to balance the tradeoff between maximizing accuracy and minimizing the perception of bias in the classification decisions. Using a graphtheoretic framework, we present a theoretical bound on the gap between the true positive rates for different groups of individuals when fairness perception is maximized. Finally, we investigate the network sampling problem from a fairness perspective. Specifically, we propose a novel fairnessaware network sampling framework that combines the structural preservability and group representativity objectives into a unified structure. We also present a fair greedy sampling algorithm with bounded approximation guarantees.
Show less
 Title
 Distancepreserving graphs
 Creator
 Nussbaum, Ronald
 Date
 2014
 Collection
 Electronic Theses & Dissertations
 Description

Let G be a simple graph on n vertices, where d_G(u,v) denotes the distance between vertices u and v in G. An induced subgraph H of G is isometric if d_H(u,v)=d_G(u,v) for all u,v in V(H). We say that G is a distancepreserving graph if G contains at least one isometric subgraph of order k for every k where 1<=k<=n.A number of sufficient conditions exist for a graph to be distancepreserving. We show that all hypercubes and graphs with delta(G)>=2n/31 are distancepreserving. Towards this end...
Show moreLet G be a simple graph on n vertices, where d_G(u,v) denotes the distance between vertices u and v in G. An induced subgraph H of G is isometric if d_H(u,v)=d_G(u,v) for all u,v in V(H). We say that G is a distancepreserving graph if G contains at least one isometric subgraph of order k for every k where 1<=k<=n.A number of sufficient conditions exist for a graph to be distancepreserving. We show that all hypercubes and graphs with delta(G)>=2n/31 are distancepreserving. Towards this end, we carefully examine the role of "forbidden" subgraphs. We discuss our observations, and provide some conjectures which we computationally verified for small values of n. We say that a distancepreserving graph is sequentially distancepreserving if each subgraph in the set of isometric subgraphs is a superset of the previous one, and consider this special case as well.There are a number of questions involving the construction of distancepreserving graphs. We show that it is always possible to add an edge to a noncomplete sequentially distancepreserving graph such that the augmented graph is still sequentially distancepreserving. We further conjecture that the same is true of all distancepreserving graphs. We discuss our observations on making nondistancepreserving graphs into distance preserving ones via adding edges. We show methods for constructing regular distancepreserving graphs, and consider constructing distancepreserving graphs for arbitrary degree sequences. As before, all conjectures here have been computationally verified for small values of n.
Show less
 Title
 Distance preserving graphs
 Creator
 Zahedi, Emad
 Date
 2017
 Collection
 Electronic Theses & Dissertations
 Description

"The computational complexity of exploring distance properties of large graphs such as realworld social networks which consist of millions of nodes is extremely expensive. Recomputing distances in subgraphs of the original graph will add to the cost. One way to avoid this is to use subgraphs where the distance between any pair of vertices is the same as in the original graph. Such a subgraph is called isometric. A connected graph is distance preserving, for which we use the abbreviation dp,...
Show more"The computational complexity of exploring distance properties of large graphs such as realworld social networks which consist of millions of nodes is extremely expensive. Recomputing distances in subgraphs of the original graph will add to the cost. One way to avoid this is to use subgraphs where the distance between any pair of vertices is the same as in the original graph. Such a subgraph is called isometric. A connected graph is distance preserving, for which we use the abbreviation dp, if it has an isometric subgraph of every order. In this framework we study dp graphs from both the structural and algorithmic perspectives. First, we study the structural nature of dp graphs. This involves classifying graphs based on the dp property and the relation between dp graphs to other graph classes. Second, we study the recognition problem of dp graphs. We intend to develop efficient algorithms for finding isometric subgraphs as well as deciding whether a graph is dp or not."Page ii.
Show less
 Title
 Edge impact in graphs and social network matrix completion
 Creator
 Ross, Dennis
 Date
 2016
 Collection
 Electronic Theses & Dissertations
 Description

Every graph G can be associated with many wellknown invariant properties along with their corresponding values. A framework is proposed to measure the change in any particular invariant upon addition of a new edge $e$ in the resulting graph G+e. In graphs, the Pimpact of an edge e is the `magnitude' of the difference between the values of the invariant P in graphs G+e from G. Several famous invariants are explored and a proof towards optimal edge addition for distanceimpact in trees is...
Show moreEvery graph G can be associated with many wellknown invariant properties along with their corresponding values. A framework is proposed to measure the change in any particular invariant upon addition of a new edge $e$ in the resulting graph G+e. In graphs, the Pimpact of an edge e is the `magnitude' of the difference between the values of the invariant P in graphs G+e from G. Several famous invariants are explored and a proof towards optimal edge addition for distanceimpact in trees is given. A natural application to measuring the impact of edge addition to a graph is that of link prediction. An efficient algorithm for link prediction even with coldstart vertices using a subspace sharing method that decouples matrix completion and side information transduction is presented. This method is extended to predict ratings in useritem recommender systems where both may be coldstart.
Show less