Using eigenvectors of perturbed and collapsed adjacency matrices to explore bowtie structures in directed networks

References

• Adamic, L. A., and N. Glance. 2005. “The Political Blogosphere and the 2004 U.S. Election: Divided They Blog.” In Proceedings of the 3rd International Workshop on Link Discovery, Chicago, IL, 21–24 August 2005: 36–43. New York: ACM.
   Google Scholar
• Aho, A. V., M. R. Garey, and J. D. Ullman. 1972. “The Transitive Reduction of a Directed Graph.” SIAM Journal on Computing 1 (2): 131–137. doi:10.1137/0201008.
   Google Scholar
• Batagelj, V., A. Ferligoj, and P. Doreian. 1992. “Direct and Indirect Methods for Structural Equivalence.” Social Networks 14 (1–2): 63–90. doi:10.1016/0378-8733(92)90014-X.
   Web of Science ®Google Scholar
• Bonacich, P. 1972. “Factoring and Weighting Approaches to Status Scores and Clique Identification.” The Journal of Mathematical Sociology 2 (1): 113–120. doi:10.1080/0022250X.1972.9989806.
   Web of Science ®Google Scholar
• Bonacich, P. 1987. “Power and Centrality: A Family of Measures.” American Journal of Sociology 92 (5): 1170–1182. doi:10.1086/228631.
   Web of Science ®Google Scholar
• Bonacich, P. 2007. “Some Unique Properties of Eigenvector Centrality.” Social Networks 29 (4): 555–564. doi:10.1016/j.socnet.2007.04.002.
   Web of Science ®Google Scholar
• Bonacich, P., and P. Lloyd. 2001. “Eigenvector-like Measures of Centrality for Asymmetric Relations.” Social Networks 23 (3): 191–201. doi:10.1016/S0378-8733(01)00038-7.
   Web of Science ®Google Scholar
• Borgatti, S. P. 2002. NetDraw: Graph Visualization Software. Harvard, MA: Analytic Technologies.
   Google Scholar
• Breiger, R., S. A. Boorman, and P. Arabie. 1975. “An Algorithm for Clustering Relational Data with Applications to Social Network Analysis and Comparison with Multidimensional Scaling.” Journal of Mathematical Psychology 12 (3): 328–383. doi:10.1016/0022-2496(75)90028-0.
   Web of Science ®Google Scholar
• Brin, S., and L. Page. 1998. “The Anatomy of a Large-scale Hypertextual Web Search Engine.” Computer Networks and ISDN Systems 30 (1–7): 107–117. doi:10.1016/S0169-7552(98)00110-X.
   Web of Science ®Google Scholar
• Broder, A., R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, and J. Wiener. 2000. “Graph Structure in the Web.” Computer Networks: The International Journal of Computer and Telecommunications Networking 33 (1–6): 309–320. doi:10.1016/S1389-1286(00)00083-9.
   Web of Science ®Google Scholar
• Brualdi, R. A. 2010. “Spectra of Digraphs.” Linear Algebra and its Applications 432 (9): 2181–2213. doi:10.1016/j.laa.2009.02.033.
   Web of Science ®Google Scholar
• Burt, R. S. 1976. “Positions in Networks.” Social Forces 55 (1): 93–122. doi:10.2307/2577097.
   Web of Science ®Google Scholar
• Chung, F. R. K. 1997. Spectral Graph Theory. Providence, RI: American Mathematical Soc.
   Google Scholar
• Dill, S., R. Kumar, K. S. Mccurley, S. Rajagopalan, D. Sivakumar, and A. Tomkins. 2002. “Self-Similarity in the Web.” ACM Transactions on Internet Technology 2 (3): 205–223. doi:10.1145/572326.572328.
   Google Scholar
• Donato, D., S. Leonardi, S. Millozzi, and P. Tsaparas. 2008. “Mining the Inner Structure of the Web Graph.” Journal of Physics A: Mathematical and Theoretical 41 (22): 224017. doi:10.1088/1751-8113/41/22/224017.
   Web of Science ®Google Scholar
• Donetti, L., and M. A. Munoz. 2004. “Detecting Network Communities: A New Systematic and Efficient Algorithm.” Journal of Statistical Mechanics: Theory and Experiment 2004: P10012. doi:10.1088/1742-5468/2004/10/P10012.
   Web of Science ®Google Scholar
• Doreian, P., V. Batagelj, and A. Ferligoj. 2000. “Symmetric-acyclic Decompositions of Networks.” Journal of Classification 17 (1): 3–28. doi:10.1007/s003570000002.
   Web of Science ®Google Scholar
• Doreian, P., V. Batagelj, and A. Ferligoj. 2005. Generalized Blockmodeling. New York: Cambridge University Press.
   Google Scholar
• Fortunato, S., and A. Flammini. 2007. “Random Walks on Directed Networks: The Case of Pagerank.” International Journal of Bifurcation and Chaos 17 (7): 2343–2353. doi:10.1142/S0218127407018439.
   Web of Science ®Google Scholar
• Freeman, L. C. 1979. “Centrality in Social Networks: Conceptual Clarification.” Social Networks 1 (3): 215–239. doi:10.1016/0378-8733(78)90021-7.
   Web of Science ®Google Scholar
• Friedkin, N. E. 1991. “Theoretical Foundations for Centrality Measures.” American Journal of Sociology 96 (6): 1478–1504. doi:10.1086/229694.
   Web of Science ®Google Scholar
• Hubbell, C. H. 1965. “An Input–output Approach to Clique Identification.” Sociometry 28 (4): 377–399. doi:10.2307/2785990.
   Google Scholar
• Jones, N. 2014. “Bowtie Structures, Pathway Diagrams, and Topological Explanation.” Erkenntnis 79 (5): 1135–1155. doi:10.1007/s10670-014-9598-9.
   Web of Science ®Google Scholar
• Kannan, R., and S. Vempala. 2008. “Spectral Algorithms.” Foundations and Trends in Theoretical Computer Science 4 (3–4): 157–288. doi:10.1561/0400000025.
   Google Scholar
• Katz, L. 1953. “A New Status Index Derived from Sociometric Analysis.” Psychometrika 18 (1): 39–43. doi:10.1007/BF02289026.
   Google Scholar
• Kleinberg, J. M. 1999. “Authoritative Sources in a Hyperlinked Environment.” Journal of the ACM 46 (5): 604–632. doi:10.1145/324133.324140.
   Web of Science ®Google Scholar
• Langville, A. N., and C. D. Meyer. 2006. Google’s PageRank and beyond: The Science of Search Engine Rankings. Princeton, NJ: Princeton University Press.
   Google Scholar
• Leskovec, J., A. Rajaraman, and J. D. Ullman. 2014. Mining of Massive Datasets. New York: Cambridge University Press.10.1017/CBO9781139924801
   Google Scholar
• Lu, N.-P. 2015. “Exploring Network Structures via Blockmodeling of the Shortest Path Length Matrix.” Journal of the Chinese Institute of Engineers 38 (8): 1080–1089. doi:10.1080/02533839.2015.1047800.
   Web of Science ®Google Scholar
• Metaxas, P. T. 2012. “Why is the Shape of the Web a Bowtie?” In Proceedings of the 21st International Conference on World Wide Web, Lyon, 16–20 April 2012: 1–5. New York: ACM.
   Google Scholar
• Moody, J. 2001. “Peer Influence Groups: Identifying Dense Clusters in Large Networks.” Social Networks 23 (4): 261–283. doi:10.1016/S0378-8733(01)00042-9.
   Web of Science ®Google Scholar
• Newman, M. E. J. 2006. “Finding Community Structure in Networks Using the Eigenvectors of Matrices.” Physical Review E 74 (3): 036104. doi:10.1103/PhysRevE.74.036104.
   Web of Science ®Google Scholar
• Richards, W., and A. Seary. 2000. “Eigen Analysis of Networks.” Journal of Social Structure 1 (2): 1–17.
   Google Scholar
• Sahni, S. 2001. Data Structures, Algorithms, and Applications in Java. New York: McGraw-Hill College.
   Google Scholar
• Seary, A. J., and W. D. Richards. 2003. “Spectral Methods for Analyzing and Visualizing Networks: An Introduction.” In Dynamic Social Network Modeling and Analysis: Workshop Summary and Papers, edited by B. Breiger, K. Carley, and P. Pattison, 209–228. Washington, DC: The National Academies Press.
   Google Scholar
• Spielman, D. 2012. “Spectral Graph Theory.” In Combinatorial Scientific Computing, edited by U. Naumann and O. Schenk, 495–524. Boca Raton, Fl: CRC Press.10.1201/CHCOMPUTSCI
   Google Scholar
• Sternberg, S. 2010. Dynamical Systems. New York: Dover Publications.
   Google Scholar
• Tarjan, R. 1972. “Depth-first Search and Linear Graph Algorithms.” SIAM Journal on Computing 1 (2): 146–160. doi:10.1137/0201010.
   Google Scholar
• Vitali, S., J. B. Glattfelder, and S. Battiston. 2011. “The Network of Global Corporate Control.” PLoS ONE 6 (10): e25995. doi:10.1371/journal.pone.0025995.
   PubMed Web of Science ®Google Scholar
• Wasserman, S., and K. Faust. 1994. Social Network Analysis: Methods and Applications. Cambridge: Cambridge University Press.10.1017/CBO9780511815478
   Google Scholar
• Weeks, M. R., S. Clair, S. P. Borgatti, K. Radda, and J. J. Schensul. 2002. “Social Networks of Drug Users in High-risk Sites: Finding the Connections.” AIDS and Behavior 6 (2): 193–206. doi:10.1023/A:1015457400897.
   Google Scholar
• White, H. C., S. A. Boorman, and R. L. Breiger. 1976. “Social Structure from Multiple Networks: I. Blockmodels of Roles and Positions.” American Journal of Sociology 81 (4): 730–780. doi:10.1086/226141.
   Web of Science ®Google Scholar
• Yang, R., L. Zhuhadar, and O. Nasraoui. 2011. “Bow-tie Decomposition in Directed Graphs.” In Proceedings of the 14th International Conference on Information Fusion, Chicago, IL, 5–8 July 2011: 1–5. New York: IEEE.
   Google Scholar
• Zhang, J., M. S. Ackerman, and L. Adamic. 2007. “Expertise Networks in Online Communities: Structure and Algorithms.” In Proceedings of the 16th International Conference on World Wide Web, Banff, AB, Canada, 8–12 May 2007: 221–230. New York: ACM.
   Google Scholar
• Zhao, J., H. Yu, J.-H. Luo, Z.-W. Cao, and Y.-X. Li. 2006. “Hierarchical Modularity of Nested Bow-ties in Metabolic Networks.” BMC Bioinformatics 7: 1–16. doi:10.1186/1471-2105-7-386.
   PubMed Web of Science ®Google Scholar