Node position and similarity

Measures of node position and centrality, measures of link importance and bridging, and link analysis algorithms. Node similarity and equivalence.

Lectures materials:

• Measures of node centrality (slides)
• Node similarity and equivalence (slides)
• Measures of link bridging (slides)
• Link analysis algorithms (slides)
  

Book chapters:

• Ch. 7: Measures and metrics in Newman, M.E.J., Networks: An Introduction (Oxford University Press, 2010).
  
• Ch. 14: Link analysis and web search in Easley, D. & Kleinberg, J., Networks, Crowds, and Markets (Cambridge University Press, 2010).
• Ch. 14: Classical node centrality & Ch. 15: Spectral etc. in Estrada, E. & Knight, P.A., A First Course in Network Theory (Oxford University Press, 2015).

Course readings:

• Katz, L., A new status index derived from sociometric analysis, Psychometrika 18(1), 39-43 (1953).
  
• Freeman, L.C., A set of measures of centrality based on betweenness, Sociometry 40(1), 35-41 (1977).
• Freeman, L.C., Centrality in social networks: Conceptual clarification, Soc. Networks 1(3), 215-239 (1979).
  
• Bonacich, P., Power and centrality: A family of measures, Am. J. Sociology 92(5), 1170-1182 (1987).
• Brandes, U., A faster algorithm for betweenness centrality, J. Math. Sociol. 25(2), 163-177 (2001).
• Jeong, H., Mason, S.P., et al., Lethality and centrality in protein networks, Nature 411, 41-42 (2001).
• Soffer, S.N. & Vázquez, A., Network clustering coefficient without degree-correlation biases, Phys. Rev. E 71(5), 057101 (2005).
• Newman, M.E.J., A measure of betweenness centrality based on random walks, Soc. Networks 27(1), 39-54 (2005).
• Jensen, P., Morini, M., et al., Detecting global bridges in networks, J. Complex Netw., 1-15 (2015), under review.
• Everett, M.G. & Valente, T.W., Bridging, brokerage and betweenness, Soc. Networks 44, 202-208 (2016).
• Franceschet, M. & Bozzo, E., A theory on power in networks, e-print arXiv:1510.08332v2, pp. 19 (2016).
• Agneessens, F., Borgatti, S.P. & Everett, M.G., Geodesic based centrality, Soc. Networks 49, 12-26 (2017).
• Wu, A.-K., Tian, L. & Liu, Y.-Y., Bridges in complex networks, Phys. Rev. E 97(1), 012307 (2018).
  

• Lorrain, F. & White, H.C., Structural equivalence of individuals in social networks, J. Math. Sociol. 1(1), 49-80 (1971).
  
• White, D.R., & Reitz, K.P., Graph and semigroup homomorphisms on networks of relations, Soc. Networks 5(2), 193-234 (1983).
  
• Leicht, E.A., Holme, P. & Newman, M.E.J., Vertex similarity in networks, Phys. Rev. E 73(2), 026120 (2006).
  
• Onnela, J.-P., Saramäki, J., et al., Structure and tie strengths in mobile communication networks, P. Natl. Acad. Sci. USA 104(18), 7332-7336 (2007).
  
• Liben‐Nowell, D. & Kleinberg, J., The link‐prediction problem for social networks, J. Am. Soc. Inf. Sci. Tec. 58(7), 1019-1031 (2007).
  
• Zhou, T., Lü, L. & Zhang, Y.-C., Predicting missing links via local information, Eur. Phys. J. B 71(4), 623-630 (2009).

• Kleinberg, J., Authoritative sources in a hyperlinked environment, J. ACM 46(5), 604-632 (1999).
• Brin, S. & Page, L., The anatomy of a large-scale hypertextual Web search engine, Comput. Networks ISDN 30(1-7), 107-117 (1998).
• Lempel, R. & Moran, S., SALSA: The stochastic approach for link-structure analysis, ACM Trans. Inf. Syst. 19(2), 131–160 (2001).
• Haveliwala, T.H., Topic-sensitive PageRank, In: Proceedings of WWW ’02 (Honolulu, HI, USA, 2002), pp. 517-526.
• Jeh, G. & Widom, J., SimRank: A measure of structural-context similarity, In: Proceedings of KDD ’02 (Edmonton, Canada, 2002), pp. 538–543.
  
• Gyongyi, Z., Garcia-Molina, H. & Pedersen, J., Combating web spam with TrustRank, In: Proceedings of VLDB ’04 (Toronto, Canada, 2004), pp. 576-587.
  
• Tong, H., Faloutsos, C. & Pan, J.-Y., Fast random walk with restart and its applications, In: Proceedings of ICDM ’06 (Washington, DC, USA, 2006), pp. 613-622.
  
• Berkhin, P., A survey on PageRank computing, Internet Math. 2(1), 73-120 (2005).
  
• Fabrikant, A., Mahdian, M. & Tomkins, A., SCRank, e-print arXiv:1802.08204v1, pp. 10 (2018).