Social resistance

PDF DOI Computing Edge

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.

BiBTeX

@ARTICLE{Friedlander2016social,
  author = {M. P. {Friedlander} and N. {Krislock} and T. K. {Pong}},
  journal = {Computing in Science and Engineering}, 
  title = {Social Resistance}, 
  year = {2016},
  volume = {18},
  number = {2},
  pages = {98-103},
  abstract = {Can we measure how close two people in a social network are just by knowing who is friends with whom? Can we infer the closeness of two people's research areas just by observing coauthor relations? Can we predict the importance of new roads just by looking at a current traffic network? In this case study, the authors investigate an approach to these questions and the algorithms behind the computations.},
  keywords={social sciences computing;social resistance;social network;coauthor relations;closeness factor;traffic network;Resistance;MATLAB;Sparse matrices;Collaboration;Social network services;Symmetric matrices;Laplace equations;resistance distance;networks;rank-one Cholesky update;education;scientific computing},
  doi = {10.1109/MCSE.2016.30},
  ISSN = {1558-366X},
  month = {Mar}
}