Measuring and Mitigating the Impact of Network Bias on Computation in Graphs
Abstract
The Offeror will address the notion of Network Bias, first noticed in the context of Social Network Analysis, prevalent in processing large graphs using local information based algorithms. Due to the fact that processing large graphs in memory (of a single processor) is impossible, distributed algorithms (such as those based on belief propagation) are commonly used that rely on local information. Network bias is the difference in conclusion obtained by processing data locally vs being able to make use of information about the entire graph. The PI will investigate the connection between the structure of a graph and network bias it could entail. Finally, the PI will also consider methods to mitigate network bias. The Offeror will develop analytical characterization of network bias based on second order properties of degree distributions and structure of the graph. The analytical model will then be used to devise a class of belief propagation algorithms that are aware of network bias. Finally, the analytical and computational model will be tested against data on social networks (which exhibit network bias in the form of friendship paradox, for instance).
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Jan 12, 2017
- Source ID
- W911NF1610306
Entities
People
- Kristina Lerman
Organizations
- Army Contracting Command
- United States Army
- University of Southern California