Social Resistance

M. P. Friedlander, N. Krislock, T. K. Pong
IEEE Computing in Science and Engineering and Computing Edge, 2016

PDF

Abstract

This case study concerns an important question in social networks: How closely related are two people in a network? We measure the strength of the relationship between two people in terms of their resistance distance, a notion of distance that has its origin in the study of electrical networks. In that context, the resistance distance measures the electrical resistance between the two nodes in a network, assuming unit resistance on each edge. Its relationship with the information distance in social networks was recently identified. For large networks, this distance measure can be expensive to compute. As the network changes, it’s useful to have an inexpensive way to make updates. We’ll study how various techniques for updating matrix factorizations can help efficiently compute the resistance distances with small changes in the network. We focus on Cholesky rank-one updates, and also briefly discuss the Sherman-Morrison-Woodbury formula (as one of the last exercises). We expect that you’re familiar with the idea of the Cholesky factorization of positive definite matrices. We’ll guide you through a derivation of the formula for the Cholesky rank-one update, and introduce two aspects that maybe new for you. First, you’ll have to figure out the vector used for the rank-one update when one additional connection in the network is identified. Second, when matrices are large, you’ll observe that there can be a big difference in computational effort when the computation involves matrix-matrix multiplications rather than only matrix-vector multiplications.