Axioms for Centrality

References

• [Anthonisse 71] Jac M. Anthonisse. “The Rush in a Graph.” Technical Report, Amsterdam: University of Amsterdam Mathematical Centre, 1971.
   Google Scholar
• [Altman and Tennenholtz 05] Alon Altman and Moshe Tennenholtz. “Ranking Systems: The PageRank Axioms.” In Proceedings of the 6th ACM Conference on Electronic Commerce, pp. 1–8. New York, NY: ACM, 2005.
   Google Scholar
• [Avrachenkov and Litvak 06] Konstantin Avrachenkov and Nelly Litvak. “The Effect of New Links on Google PageRank.” Stochastic Models 22:2 (2006), 319–331.
   Web of Science ®Google Scholar
• [Backstrom et al. 12] Lars Backstrom, Paolo Boldi, Marco Rosa, Johan Ugander, and Sebastiano Vigna. “Four Degrees of separation.” In ACM Web Science 2012: Conference Proceedings, pp. 45–54. ACM Press, 2012.
   Google Scholar
• [Bavelas 50] Alex Bavelas. “Communication Patterns in Task-Oriented Groups.” Journal of Acoustical Socciety of America 22:6 (1950), 725–730.
   Web of Science ®Google Scholar
• [Bavelas and Barrett 51] A. Bavelas, D. Barrett, and American Management Association. An Experimental Approach to Organizational Communication. Publications (Massachusetts Institute of Technology. Dept. of Economics and Social Science): Industrial Relations. American Management Association, 1951.
   Google Scholar
• [Beauchamp 65] Murray A. Beauchamp. “An Improved Index of Centrality.” Behavioral Science 10:2 (1965), 161–163.
   PubMedGoogle Scholar
• [Berge 58] Claude Berge. Théorie des Graphes et ses Applications. Paris, France:Dunod, 1958.
   Google Scholar
• [Berman and Plemmons 94] Abraham Berman and Robert J. Plemmons. Nonnegative Matrices in the Mathematical Sciences. Classics in Applied Mathematics. SIAM, 1994.
   Google Scholar
• [Boldi et al.13] Paolo Boldi, Marco Rosa, and Sebastiano Vigna. “Robustness of Social and Web Graphs to Node Removal.” Social Network Analysis and Mining 3:4 (2013), 829–842.
   Google Scholar
• [Boldi et al. 05] Paolo Boldi, Massimo Santini, and Sebastiano Vigna. “PageRank as a Function of the Damping factor.” In Proc. of the Fourteenth International World Wide Web Conference (WWW 2005), pp. 557–566. Chiba, Japan, 2005. ACM Press, 2005.
   Google Scholar
• [Boldi et al. 09] Paolo Boldi, Massimo Santini, and Sebastiano Vigna. “PageRank: Functional Dependencies.” ACM Trans. Inf. Sys. 27:4 (2009), 1–23.
   Web of Science ®Google Scholar
• [Boldi and Vigna 13] Paolo Boldi and Sebastiano Vigna. “In-Core Computation of Geometric Centralities with HyperBall: A Hundred Billion Nodes and Beyond.” In Proc. of 2013 IEEE 13th International Conference on Data Mining Workshops (ICDMW 2013). IEEE, 2013.
   Google Scholar
• [Bonacich 72] Phillip Bonacich. “Factoring and Weighting Approaches to Status Scores and Clique Identification.” Journal of Mathematical Sociology 2:1 (1972), 113–120.
   Web of Science ®Google Scholar
• [Bonacich 91] Phillip Bonacich. “Simultaneous Group and Individual Centralities.” Social Networks 13:2 (1991), 155–168.
   Web of Science ®Google Scholar
• [Borgatti 05] Stephen P. Borgatti. “Centrality and Network Flow.” Social Networks 27:1 (2005), 55–71.
   Web of Science ®Google Scholar
• [Borodin et al. 05] Allan Borodin, Gareth O. Roberts, Jeffrey S. Rosenthal, and Panayiotis Tsaparas. “Link analysis Ranking: Algorithms, Theory, and Experiments.” ACM Transactions on Internet Technology (TOIT) 5:1 (2005), 231–297.
   Google Scholar
• [Brandes et al. 12] Ulrik Brandes, Sven Kosub, and Bobo Nick. “Was messen Zentralitätsindizes?” In Die Integration von Theorie und Methode in der Netzwerkforschung, edited by Marina Hennig and Christian Stegbauer, pp. 33–52. VS Verlag für Sozialwissenschaften, 2012.
   Google Scholar
• [Brauer 52] Alfred Brauer. “Limits for the Characteristic Roots of a Matrix. IV: Applications to Stochastic Matrices.” Duke Math. J. 19:1 (1952), 75–91.
   Web of Science ®Google Scholar
• [Brin and Page 98] Sergey Brin and Lawrence Page. “The Anatomy of a Large-Scale Hypertextual Web Search Engine.” Computer Networks and ISDN Systems 30:1 (1998), 107–117.
   Web of Science ®Google Scholar
• [Burgess 69] Robert L. Burgess. “Communication Networks and Behavioral Consequences.” Human Relations 22:2 (1969), 137–159.
   Web of Science ®Google Scholar
• [Chien et al. 04] Steve Chien, Cynthia Dwork, Ravi Kumar, Daniel R. Simon, and D. Sivakumar. “Link Evolution: Analysis and Algorithms.” Internet Math. 1:3 (2004), 277–304.
   Google Scholar
• [Cohen and Kaplan 07] Edith Cohen and Haim Kaplan. “Spatially-Decaying Aggregation over a Network.” Journal of Computer and System Sciences 73:3 (2007), 265–288.
   Web of Science ®Google Scholar
• [Cohen and Havlin 10] Reuven Cohen and Shlomo Havlin. Complex Networks: Structure, Robustness and Function. New York, NY: Cambridge University Press, 2010.
   Google Scholar
• [Cohn and Marriott 58] B.S. Cohn and M. Marriott. “Networks and Centres of Integration in Indian Civilization.” Journal of Social Research 1:1 (1958), 1–9.
   Google Scholar
• [Craswell et al. 03] Nick Craswell, David Hawking, and Trystan Upstill. “Predicting Fame and Fortune: PageRank or indegree?” In Proceedings of the Australasian Document Computing Symposium, ADCS2003, pp. 31–40, 2003.
   Google Scholar
• [Del Corso et al. 06] Gianna Del Corso, Antonio Gullì, and Francesco Romani. “Fast PageRank Computation via a Sparse Linear System.” Internet Math. 2:3 (2006), 251–273.
   Google Scholar
• [Farahat et al. 06] Ayman Farahat, Thomas Lofaro, Joel C. Miller, Gregory Rae, and Lesley A. Ward. “Authority Rankings from HITS, PageRank, and SALSA: Existence, Uniqueness, and Effect of Initialization.” SIAM Journal on Scientific Computing 27:4 (2006), 1181–1201.
   Web of Science ®Google Scholar
• [Freeman 77] Linton C. Freeman. “A Set of Measures of Centrality Based on Betweenness.” Sociometry 40:1 (1977), 35–41.
   Google Scholar
• [Freeman 79] L. Freeman. “Centrality in Social Networks: Conceptual Clarification.” Social Networks 1:3 (1979), 215–239.
   Web of Science ®Google Scholar
• [Friedkin 91] N.E. Friedkin. “Theoretical Foundations for Centrality Measures.” The American Journal of Sociology 96:6 (1991), 1478–1504.
   Web of Science ®Google Scholar
• [Hubbell 65] Charles H. Hubbell. “An Input-Output Approach to Clique Identification.” Sociometry 28:4 (1965), 377–399.
   Google Scholar
• [Järvelin and Kekäläinen 02] Kalervo Järvelin and Jaana Kekäläinen. “Cumulated Gain-Based Evaluation of IR Techniques.” ACM Trans. Inf. Syst. 20:4 (2002), 422–446.
   Web of Science ®Google Scholar
• [Katz 53] Leo Katz. “A New Status Index Derived from Sociometric Analysis.” Psychometrika 18:1 (1953), 39–43.
   Google Scholar
• [Kendall 55] Maurice G. Kendall. “Further Contributions to the Theory of Paired Comparisons.” Biometrics 11:1 (1955), 43–62.
   Web of Science ®Google Scholar
• [Kleinberg 99] Jon M. Kleinberg. “Authoritative Sources in a Hyperlinked Environment.” Journal of the ACM 46: (1999), 604–632.
   Web of Science ®Google Scholar
• [Knuth 92] Donald E. Knuth. “Two Notes on Notation.” American Mathematical Monthly 99:5 (1992), 403–422.
   Web of Science ®Google Scholar
• [Leavitt 51] H. J. Leavitt. “Some Effects of Certain Communication Patterns on Group Performance.” J. Abnorm. Psychol. 46:1 (1951), 38–50.
   PubMed Web of Science ®Google Scholar
• [Lempel and Moran 01] Ronny Lempel and Shlomo Moran. “SALSA: The Stochastic Approach for Link-Structure Analysis.” ACM Trans. Inf. Syst. 19:2 (2001), 131–160.
   Web of Science ®Google Scholar
• [Lempel and Moran 05] Ronny Lempel and Shlomo Moran. “Rank-Stability and Rank-Similarity of Link-Based Web Ranking Algorithms in Authority-Connected Graphs.” Information Retrieval 8:2 (2005), 245–264.
   Web of Science ®Google Scholar
• [Li et al. 05] Lun Li, David L. Alderson, John Doyle, and Walter Willinger. “Towards a Theory of Scale-Free Graphs: Definition, Properties, and Implications.” Internet Math. 2:4 (2005), 431–523.
   Google Scholar
• [Lin 76] Nan Lin. Foundations of Social Research. McGraw-Hill, New York, 1976.
   Google Scholar
• [Mackenzie 66] Kenneth Mackenzie. “Structural Centrality in Communications Networks.” Psychometrika 31:1 (1966), 17–25.
   Web of Science ®Google Scholar
• [Marchiori and Latora 00] Massimo Marchiori and Vito Latora. “Harmony in the Small-World.” Physica A: Statistical Mechanics and its Applications 285:3–4 (2000), 539–546.
   Google Scholar
• [McDonald et al. 95] J.J. McDonald, M. Neumann, H. Schneider, and M.J. Tsatsomeros. “Inverse m-Matrix Inequalities and Generalized Ultrametric Matrices.” Linear Algebra and its Applications 220 (1995), 321–341.
   Web of Science ®Google Scholar
• [Milgram 67] Stanley Milgram. “The Small World Problem.” Psychology Today 2:1 (1967), 60–67.
   Google Scholar
• [Najork et al. 09] Marc Najork, Sreenivas Gollapudi, and Rina Panigrahy. “Less is More: Sampling the Neighborhood Graph Makes SALSA Better and Faster.” In Proceedings of the Second ACM International Conference on Web Search and Data Mining, pp. 242–251. New York, NY: ACM, 2009.
   Google Scholar
• [Najork et al. 07a] Marc Najork, Hugo Zaragoza, and Michael J. Taylor. “HITS on the Web: How Does it Compare?” In Wessel Kraaij, Arjen P. de Vries, Charles L. A. Clarke, Norbert Fuhr, and Noriko Kando, pp. 471–478. SIGIR 2007: Proceedings of the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. Amsterdam, The Netherlands: New York, NY: ACM, 2007.
   Google Scholar
• [Najork et al. 07b] Marc A. Najork, Hugo Zaragoza, and Michael J. Taylor. HITS on the web: How does it compare? In Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, SIGIR ‘07, pages 471–478. ACM, 2007.
   Google Scholar
• [Nieminen 73] U.J. Nieminen. “On the Centrality in a Directed Graph.” Social Science Research 2:4 (1973), 371–378.
   Google Scholar
• [Padgett and Ansell 93] John F. Padgett and Christopher K. Ansell. “Robust Action and the Rise of the Medici, 1400–1434”. The American Journal of Sociology 98:6 (1993), 1259–1319.
   Web of Science ®Google Scholar
• [Page et al. 98] Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. “The PageRank Citation Ranking: Bringing Order to the Web.” Technical Report SIDL-WP-1999-0120, Stanford Digital Library Technologies Project, Stanford University, 1998.
   Google Scholar
• [Pan and Saramäki 11] Raj Kumar Pan and Jari Saramäki. “Path Lengths, Correlations, and Centrality in Temporal Networks.” Phys. Rev. E 84:1 (2011), 016105.
   Web of Science ®Google Scholar
• [Pitts 65] Forrest R. Pitts. “A Graph Theoretic Approach to Historical Geography.” The Professional Geographer 17:5 (1965), 15–20.
   Web of Science ®Google Scholar
• [Sabidussi 66] G. Sabidussi. “The Centrality Index of a Graph.” Psychometrika 31:4 (1966), 581–603.
   PubMed Web of Science ®Google Scholar
• [Seeley 49] John R. Seeley. “The Net of Reciprocal Influence: A Problem in Treating Sociometric Data.” Canadian Journal of Psychology 3:4 (1949), 234–240.
   Google Scholar
• [Shannon 148] Claude E. Shannon. “A Mathematical Theory of Communication.” Bell Syst. Tech. J. 27:3 (1948), 379–423, 623–656.
   Google Scholar
• [Stephenson and Zelen 89] Karen Stephenson and Marvin Zelen. “Rethinking Centrality: Methods and Examples.” Social Networks 11:1 (1989), 1–37.
   Web of Science ®Google Scholar
• [Upstill et al. 03] Trystan Upstill, Nick Craswell, and David Hawking. “Query-Independent Evidence in Home Page Finding.” ACM Trans. Inf. Syst. 21:3 (2003), 286–313.
   Web of Science ®Google Scholar
• [van den Brink and Gilles 94] René van den Brink and Robert P. Gilles. “A Social Power Index for Hierarchically Structured Populations of Economic Agents.” In Imperfections and Behavior in Economic Organizations, vol. 11 edited by Robert P. Gilles and Pieter H. M. Ruys, pp. 279–318. Netherlands: Springer, 1994.
   Google Scholar
• [Vigna 09] Sebastiano Vigna. “Spectral Ranking.” Preprint, 2009. (http: //arxiv.org/abs/0912.0238).
   Google Scholar
• [Wasserman and Faust 94] Stanley Wasserman and Katherine Faust. Social Network Analysis: Methods and Applications. New York, Cambridge: Cambridge Univ Press, 1994.
   Google Scholar
• [Wei 52] T.-H. Wei. The Algebraic Foundations of Ranking Theory. PhD thesis, University of Cambridge, 1952.
   Google Scholar