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 subject-related tasks has resulted in growing concerns about the inherent biases within such automated decision-making algorithms. In response to these concerns, we are witnessing a growing body of literature that focuses on designing fairness-aware machine learning algorithms. However, current fairness research is mostly limited to non-relational, independent and identically-distributed (i.i.d) data. To overcome this limitation, this thesis aims to...
Show moreThe use of machine learning in human subject-related tasks has resulted in growing concerns about the inherent biases within such automated decision-making algorithms. In response to these concerns, we are witnessing a growing body of literature that focuses on designing fairness-aware machine learning algorithms. However, current fairness research is mostly limited to non-relational, independent and identically-distributed (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 fairness-aware 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 fairness-aware classification algorithm is developed to balance the trade-off between maximizing accuracy and minimizing the perception of bias in the classification decisions. Using a graph-theoretic 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 fairness-aware 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
- Distance-preserving 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 distance-preserving 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 distance-preserving. We show that all hypercubes and graphs with delta(G)>=2n/3-1 are distance-preserving. 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 distance-preserving 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 distance-preserving. We show that all hypercubes and graphs with delta(G)>=2n/3-1 are distance-preserving. 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 distance-preserving graph is sequentially distance-preserving 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 distance-preserving graphs. We show that it is always possible to add an edge to a non-complete sequentially distance-preserving graph such that the augmented graph is still sequentially distance-preserving. We further conjecture that the same is true of all distance-preserving graphs. We discuss our observations on making non-distance-preserving graphs into distance preserving ones via adding edges. We show methods for constructing regular distance-preserving graphs, and consider constructing distance-preserving 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 real-world 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 real-world 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 well-known 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 P-impact 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 distance-impact in trees is...
Show moreEvery graph G can be associated with many well-known 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 P-impact 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 distance-impact 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 cold-start vertices using a subspace sharing method that decouples matrix completion and side information transduction is presented. This method is extended to predict ratings in user-item recommender systems where both may be cold-start.
Show less