@misc{ugander2011anatomy,
  abstract = {We study the structure of the social graph of active Facebook users, the
largest social network ever analyzed. We compute numerous features of the graph
including the number of users and friendships, the degree distribution, path
lengths, clustering, and mixing patterns. Our results center around three main
observations. First, we characterize the global structure of the graph,
determining that the social network is nearly fully connected, with 99.91% of
individuals belonging to a single large connected component, and we confirm the
"six degrees of separation" phenomenon on a global scale. Second, by studying
the average local clustering coefficient and degeneracy of graph neighborhoods,
we show that while the Facebook graph as a whole is clearly sparse, the graph
neighborhoods of users contain surprisingly dense structure. Third, we
characterize the assortativity patterns present in the graph by studying the
basic demographic and network properties of users. We observe clear degree
assortativity and characterize the extent to which "your friends have more
friends than you". Furthermore, we observe a strong effect of age on friendship
preferences as well as a globally modular community structure driven by
nationality, but we do not find any strong gender homophily. We compare our
results with those from smaller social networks and find mostly, but not
entirely, agreement on common structural network characteristics.},
  author = {Ugander, Johan and Karrer, Brian and Backstrom, Lars and Marlow, Cameron},
  interhash = {968abebf69b5959d2837eefcda3a8a32},
  intrahash = {efad3d029704f09829373a443eeefdde},
  note = {cite arxiv:1111.4503Comment: 17 pages, 9 figures, 1 table},
  title = {The Anatomy of the Facebook Social Graph},
  url = {http://arxiv.org/abs/1111.4503},
  year = 2011
}

@inproceedings{zesch2007analysis,
  abstract = {In this paper, we discuss two graphs in Wikipedia (i) the article graph, and (ii) the category graph. We perform a graph-theoretic analysis of the category graph, and show that it is a scale-free, small world graph like other well-known lexical semantic networks. We substantiate our findings by transferring semantic relatedness algorithms defined on WordNet to the Wikipedia category graph. To assess the usefulness of the category graph as an NLP resource, we analyze its coverage and the performance of the transferred semantic relatedness algorithms. },
  address = {Rochester},
  author = {Zesch, Torsten and Gurevych, Iryna},
  booktitle = {Proceedings of the TextGraphs-2 Workshop (NAACL-HLT)},
  interhash = {0401e62edb9bfa85dd498cb40301c0cb},
  intrahash = {332ed720a72bf069275f93485432314b},
  month = apr,
  pages = {1--8},
  publisher = {Association for Computational Linguistics},
  title = {Analysis of the Wikipedia Category Graph for NLP Applications},
  url = {http://acl.ldc.upenn.edu/W/W07/W07-02.pdf#page=11},
  year = 2007
}

@misc{batagelj2003algorithm,
  abstract = {The structure of large networks can be revealed by partitioning them to
smaller parts, which are easier to handle. One of such decompositions is based
on $k$--cores, proposed in 1983 by Seidman. In the paper an efficient, $O(m)$,
$m$ is the number of lines, algorithm for determining the cores decomposition
of a given network is presented.},
  author = {Batagelj, V. and Zaversnik, M.},
  interhash = {63be428635128d4eebd095e2ca44cdf2},
  intrahash = {d533733cd010732a5ca81417f4deca0a},
  note = {cite arxiv:cs/0310049},
  title = {An O(m) Algorithm for Cores Decomposition of Networks},
  url = {http://arxiv.org/abs/cs/0310049},
  year = 2003
}

@article{seidman1983network,
  abstract = {Social network researchers have long sought measures of network cohesion, Density has often been used for this purpose, despite its generally admitted deficiencies. An approach to network cohesion is proposed that is based on minimum degree and which produces a sequence of subgraphs of gradually increasing cohesion. The approach also associates with any network measures of local density which promise to be useful both in characterizing network structures and in comparing networks.},
  author = {Seidman, Stephen B.},
  doi = {10.1016/0378-8733(83)90028-X},
  interhash = {bdba8b78574faec3a7315423e29b7556},
  intrahash = {402ff073bdbfef97765e307068f59110},
  issn = {0378-8733},
  journal = {Social Networks},
  number = 3,
  pages = {269 - 287},
  title = {Network structure and minimum degree},
  url = {http://www.sciencedirect.com/science/article/pii/037887338390028X},
  volume = 5,
  year = 1983
}

@article{newman2006modularity,
  abstract = {Many networks of interest in the sciences, including social networks, computer networks, and metabolic and regulatory networks, are found to divide naturally into communities or modules. The problem of detecting and characterizing this community structure is one of the outstanding issues in the study of networked systems. One highly effective approach is the optimization of the quality function known as “modularity” over the possible divisions of a network. Here I show that the modularity can be expressed in terms of the eigenvectors of a characteristic matrix for the network, which I call the modularity matrix, and that this expression leads to a spectral algorithm for community detection that returns results of demonstrably higher quality than competing methods in shorter running times. I illustrate the method with applications to several published network data sets.},
  author = {Newman, M. E. J.},
  doi = {10.1073/pnas.0601602103},
  interhash = {e664336d414a1e21d89f30cc56f5e739},
  intrahash = {5dd9d0c2155f242393e63547d8a2347f},
  journal = {Proceedings of the National Academy of Sciences},
  number = 23,
  pages = {8577--8582},
  title = {Modularity and community structure in networks},
  volume = 103,
  year = 2006
}

@article{gansner2009drawing,
  abstract = {Information visualization is essential in making sense out of large data sets. Often, high-dimensional data are visualized as a collection of points in 2-dimensional space through  dimensionality reduction techniques. However, these traditional methods often do not capture well the underlying structural information, clustering, and neighborhoods. In this paper, we describe GMap: a practical tool for visualizing relational data with geographic-like maps. We illustrate the effectiveness of this approach with examples from several domains All the maps referenced in this paper can be found in http://www.research.att.com/~yifanhu/GMap },
  author = {Gansner, Emden R. and Hu, Yifan and Kobourov, Stephen G.},
  interhash = {881280a1a2aa34d84322d3781f62ca90},
  intrahash = {3f9e522da9443c0a07c39009918a4a77},
  journal = {cs.CG},
  month = jul,
  title = {{GMap}: Drawing Graphs as Maps},
  url = {http://arxiv.org/abs/0907.2585},
  volume = {arXiv:0907.2585v1},
  year = 2009
}

@incollection{lerner2005assignments,
  abstract = {9.0. 9.0.1. Preliminaries 9.0.2. Role Graph 9.1. Structural Equivalence 9.1.1. Lattice of Equivalence Relations 9.1.2. Lattice of Structural Equivalences 9.1.3. Computation of Structural Equivalences 9.2. Regular Equivalence 9.2.1. Elementary Properties 9.2.2. Lattice Structure and Regular Interior 9.2.3. Computation of Regular Interior 9.2.4. The Role Assignment Problem 9.2.5. Existence of k-Role Assignments 9.3. Other Equivalences 9.3.1. Exact Role Assignments 9.3.2. Automorphic and Orbit Equivalence 9.3.3. Perfect Equivalence 9.3.4. Relative Regular Equivalence 9.4. Graphs with Multiple Relations 9.5. The Semigroup of a Graph 9.5.1. Winship-Pattison Role Equivalence 9.6. Chapter Notes},
  address = {Berlin / Heidelberg},
  affiliation = {Computer & Information Science, University of Konstanz, Box D 67, 78457 Konstanz Germany},
  author = {Lerner, Jürgen},
  booktitle = {Network Analysis},
  doi = {10.1007/978-3-540-31955-9_9},
  editor = {Brandes, Ulrik and Erlebach, Thomas},
  interhash = {59200f990b15e99c7ab3df74fcb8443e},
  intrahash = {7385d25825c7692ffdc9b12b0ed85989},
  pages = {216-252},
  publisher = {Springer},
  series = {Lecture Notes in Computer Science},
  title = {Role Assignments},
  url = {http://dx.doi.org/10.1007/978-3-540-31955-9_9},
  volume = 3418,
  year = 2005
}

@article{journals/corr/abs-1006-1260,
  author = {Isella, Lorenzo and Stehlé, Juliette and Barrat, Alain and Cattuto, Ciro and Pinton, Jean-François and den Broeck, Wouter Van},
  ee = {http://arxiv.org/abs/1006.1260},
  interhash = {4a20da6d41e4c1e86e8c04c47b22237c},
  intrahash = {53c0555c19fbfd6af5952e2a3abcbdd2},
  journal = {CoRR},
  note = {informal publication},
  title = {What's in a crowd? Analysis of face-to-face behavioral networks},
  url = {http://dblp.uni-trier.de/db/journals/corr/corr1006.html#abs-1006-1260},
  volume = {abs/1006.1260},
  year = 2010
}

@article{citeulike:90557,
  abstract = {Systems as diverse as genetic networks or the World Wide Web are best described as networks with complex topology. A common property of many large networks is that the vertex connectivities follow a scale-free power-law distribution. This feature was found to be a consequence of two generic mechanisms: (i) networks expand continuously by the addition of new vertices, and (ii) new vertices attach preferentially to sites that are already well connected. A model based on these two ingredients reproduces the observed stationary scale-free distributions, which indicates that the development of large networks is governed by robust self-organizing phenomena that go beyond the particulars of the individual systems.},
  address = {Department of Physics, University of Notre Dame, Notre Dame, IN 46556, USA.},
  author = {Barabasi, A. L. and Albert, R.},
  citeulike-article-id = {90557},
  interhash = {89d3f086051d18093558698788063dfe},
  intrahash = {8e36ff86b30d57b43045d6ad0de2c0a5},
  issn = {0036-8075},
  journal = {Science},
  month = {October},
  number = 5439,
  pages = {509--512},
  posted-at = {2006-02-08 01:49:16},
  priority = {2},
  title = {Emergence of scaling in random networks},
  url = {http://view.ncbi.nlm.nih.gov/pubmed/10521342},
  volume = 286,
  year = 1999
}

@article{New03,
  author = {Newman, M. E. J.},
  interhash = {7bedd01cb4c06af9f5200b0fb3faa571},
  intrahash = {f0de28071b8ee1c3675e67c7538e806a},
  journal = {SIAM Review},
  number = 2,
  pages = {167-256},
  title = {The structure and function of complex networks},
  volume = 45,
  year = 2003
}

@misc{Nicosia2008,
  abstract = {  Complex networks topologies present interesting and surprising properties,
such as community structures, which can be exploited to optimize communication,
to find new efficient and context-aware routing algorithms or simply to
understand the dynamics and meaning of relationships among nodes. Complex
networks are gaining more and more importance as a reference model and are a
powerful interpretation tool for many different kinds of natural, biological
and social networks, where directed relationships and contextual belonging of
nodes to many different communities is a matter of fact. This paper starts from
the definition of modularity function, given by M. Newman to evaluate the
goodness of network community decompositions, and extends it to the more
general case of directed graphs with overlapping community structures.
Interesting properties of the proposed extension are discussed, a method for
finding overlapping communities is proposed and results of its application to
benchmark case-studies are reported. We also propose a new dataset which could
be used as a reference benchmark for overlapping community structures
identification.
},
  author = {Nicosia, V. and Mangioni, G. and Carchiolo, V. and Malgeri, M.},
  interhash = {06d111f009747dda641e0b28e7777ce0},
  intrahash = {7d8bb9ffc0402259940814addb6954c5},
  note = {cite arxiv:0801.1647
Comment: 22 pages, 11 figures},
  title = {Extending the definition of modularity to directed graphs with
  overlapping communities},
  url = {http://arxiv.org/abs/0801.1647},
  year = 2008
}

@article{PhysRevLett.100.118703,
  author = {Leicht, E. A. and Newman, M. E. J.},
  doi = {10.1103/PhysRevLett.100.118703},
  interhash = {825411a28bde71cda1c9087fc329d963},
  intrahash = {93726cc0540f75ee1cb515b2923d69e8},
  journal = {Phys. Rev. Lett.},
  month = mar,
  number = 11,
  numpages = {4},
  pages = 118703,
  publisher = {American Physical Society},
  title = {Community Structure in Directed Networks},
  url = {http://prl.aps.org/abstract/PRL/v100/i11/e118703},
  volume = 100,
  year = 2008
}

@inproceedings{conf/hipc/HarishN07,
  author = {Harish, Pawan and Narayanan, P. J.},
  booktitle = {HiPC},
  crossref = {conf/hipc/2007},
  date = {2008-01-25},
  editor = {Aluru, Srinivas and Parashar, Manish and Badrinath, Ramamurthy and Prasanna, Viktor K.},
  ee = {http://dx.doi.org/10.1007/978-3-540-77220-0_21},
  interhash = {49830572447ff1f5fe6dd6c3879725ba},
  intrahash = {00821d3bcac5f90eb2e6b90b17464037},
  isbn = {978-3-540-77219-4},
  pages = {197-208},
  publisher = {Springer},
  series = {Lecture Notes in Computer Science},
  title = {Accelerating Large Graph Algorithms on the GPU Using CUDA.},
  url = {http://dblp.uni-trier.de/db/conf/hipc/hipc2007.html#HarishN07},
  volume = 4873,
  year = 2007
}

@article{newman01random,
  abstract = {Recent work on the structure of social networks and the internet has focused attention on graphs with distributions of vertex degree that are significantly different from the Poisson degree distributions that have been widely studied in the past. In this paper we develop in detail the theory of random graphs with arbitrary degree distributions. In addition to simple undirected, unipartite graphs, we examine the properties of directed and bipartite graphs. Among other results, we derive exact expressions for the position of the phase transition at which a giant component first forms, the mean component size, the size of the giant component if there is one, the mean number of vertices a certain distance away from a randomly chosen vertex, and the average vertex-vertex distance within a graph. We apply our theory to some real-world graphs, including the world-wide web and collaboration graphs of scientists and Fortune 1000 company directors. We demonstrate that in some cases random graphs with appropriate distributions of vertex degree predict with surprising accuracy the behavior of the real world, while in others there is a measurable discrepancy between theory and reality, perhaps indicating the presence of additional social structure in the network that is not captured by the random graph.},
  address = {Santa Fe Institute, 1399 Hyde Park Road, New Mexico 87501, USA.},
  author = {Newman, M. E. and Strogatz, S. H. and Watts, D. J.},
  citeulike-article-id = {48},
  citeulike-linkout-0 = {http://view.ncbi.nlm.nih.gov/pubmed/11497662},
  citeulike-linkout-1 = {http://www.hubmed.org/display.cgi?uids=11497662},
  citeulike-linkout-2 = {http://arxiv.org/pdf/cond-mat/0007235},
  interhash = {706d572ebbb2408b5a4ffa6978579dec},
  intrahash = {a70982281644ecba5c38afd70cc5d123},
  issn = {1539-3755},
  journal = {Phys Rev E Stat Nonlin Soft Matter Phys},
  month = {August},
  number = {2 Pt 2},
  posted-at = {2005-07-07 17:17:03},
  priority = {0},
  title = {Random graphs with arbitrary degree distributions and their applications.},
  url = {http://view.ncbi.nlm.nih.gov/pubmed/11497662},
  volume = 64,
  year = 2001
}

@book{nooy2005pajek,
  address = {New York, NY, USA},
  asin = {0521602629},
  author = {de Nooy, Wouter and Mrvar, Andrej and Batagelj, Vladimir},
  dewey = {300.285},
  ean = {9780521602624},
  interhash = {deb32e4829c9c2b16857a7ced06b89eb},
  intrahash = {114a68aea38d947757b10531d599e6b8},
  isbn = {0521602629},
  number = 27,
  publisher = {Cambridge University Press},
  series = {Structural Analysis in the Social Sciences},
  title = {Exploratory Social Network Analysis with Pajek},
  url = {http://www.amazon.com/Exploratory-Network-Analysis-Structural-Sciences/dp/0521602629%3FSubscriptionId%3D192BW6DQ43CK9FN0ZGG2%26tag%3Dws%26linkCode%3Dxm2%26camp%3D2025%26creative%3D165953%26creativeASIN%3D0521602629},
  year = 2005
}

@article{newman2002assortative,
  abstract = {A network is said to show assortative mixing if the nodes in the network that have many connections tend to be connected to other nodes with many connections. Here we measure mixing patterns in a variety of networks and find that social networks are mostly assortatively mixed, but that technological and biological networks tend to be disassortative. We propose a model of an assortatively mixed network, which we study both analytically and numerically. Within this model we find that networks percolate more easily if they are assortative and that they are also more robust to vertex removal.},
  author = {Newman, M. E. J.},
  doi = {10.1103/PhysRevLett.89.208701},
  interhash = {7265c6dc287861591f52e46b17404a08},
  intrahash = {3ba2913f29e817d122b41e8d78aeeecf},
  journal = {Physical Review Letters},
  month = oct,
  number = 20,
  pages = 208701,
  publisher = {American Physical Society},
  title = {Assortative Mixing in Networks},
  url = {http://link.aps.org/doi/10.1103/PhysRevLett.89.208701},
  volume = 89,
  year = 2002
}

@phdthesis{augeri2008graph,
  abstract = {Graphs express relationships among objects, such as the radio connectivity among nodes in unmanned vehicle swarms. Some applications may rank a swarm's nodes by their relative importance, for example, using the PageRank algorithm applied in certain search engines to order query responses. The PageRank values of the nodes correspond to a unique eigenvector that can be computed using the power method, an iterative technique based on matrix multiplication. The first result is a practical lower bound on the PageRank algorithm's execution time that is derived by applying assumptions to the PageRank perturbation's scaling value and the PageRank vector's required numerical precision. The second result establishes nodes contained in the same block of the graph's coarsest equitable partition must have equal PageRank values. The third result, the AverageRank algorithm, ensures such nodes are assigned equal PageRank values. The fourth result, the ProductRank algorithm, reduces the time needed to find the PageRank vector by eliminating certain dot products in the power method if the graph's coarsest equitable partition contains blocks composed of multiple vertices. The fifth result, the QuotientRank algorithm, uses a quotient matrix induced by the coarsest equitable partition to further reduce the time needed to compute a swarm's PageRank vector.},
  address = {Wright-Patterson Air Force Base, Ohio},
  author = {Augeri, Christopher J.},
  interhash = {ae4510331651ba7525daa04479a065ca},
  intrahash = {af40ef13e09f4dda128456130bd491de},
  month = {September},
  school = {Air Force Institute of Technology},
  title = {On Graph Isomorphism and the PageRank Algorithm},
  url = {http://oai.dtic.mil/oai/oai?verb=getRecord&metadataPrefix=html&identifier=ADA490530},
  year = 2008
}

@article{freeman1993galois,
  abstract = {Galois lattices are introduced as a device to provide a general representation for two mode social network data. It is shown that Galois lattices yield a single visual image of such data in cases where most alternative models produce dual images. The inzage provided by the Galois lattice produces, moreover, an inzage that can suggest useful insights about the structural properties of the data. An example, based on data from Davis, Gardner, and Gardner (1941), is used to spell out in detail the kinds of structural insights that can be gained from this approach. In addition, other potential applications are suggested.},
  author = {Freeman, L.C. and White, D.R.},
  interhash = {8231848d3051b517f6dc33e54e6e76d2},
  intrahash = {50103469c4e839b6f05a522eaacaa3a8},
  journal = {Sociological Methodology},
  pages = {127--146},
  title = {Using Galois Lattices to Represent Network Data},
  url = {http://www.polisci.berkeley.edu/courses/coursepages/Fall2004/ps289/Galois.pdf},
  volume = 23,
  year = 1993
}

@article{barber2007mac,
  abstract = {The modularity of a network quantifies the extent, relative to a null model network, to which vertices cluster into community groups. We define a null model appropriate for bipartite networks, and use it to define a bipartite modularity. The bipartite modularity is presented in terms of a modularity matrix B; some key properties of the eigenspectrum of B are identified and used to describe an algorithm for identifying modules in bipartite networks. The algorithm is based on the idea that the modules in the two parts of the network are dependent, with each part mutually being used to induce the vertices for the other part into the modules. We apply the algorithm to real-world network data, showing that the algorithm successfully identifies the modular structure of bipartite networks.},
  author = {Barber, M. J.},
  doi = {10.1103/PhysRevE.76.066102},
  interhash = {e1d9f528c49b34ff4a05b2b0060bd653},
  intrahash = {61f9d5839845d5d8fa1883a46a2f7744},
  journal = {Physical Review E},
  number = 6,
  title = {Modularity and community detection in bipartite networks},
  url = {http://arxiv.org/abs/arXiv:0707.1616},
  volume = 76,
  year = 2007
}

@article{guimera2007mib,
  abstract = {Modularity is one of the most prominent properties of real-world complex networks. Here, we address the issue of module identification in two important classes of networks: bipartite networks and directed unipartite networks. Nodes in bipartite networks are divided into two non-overlapping sets, and the links must have one end node from each set. Directed unipartite networks only have one type of nodes, but links have an origin and an end. We show that directed unipartite networks can be conviniently represented as bipartite networks for module identification purposes. We report a novel approach especially suited for module detection in bipartite networks, and define a set of random networks that enable us to validate the new approach.},
  author = {Guimer{\`a}, R. and Sales-Pardo, M. and Amaral, L.A.N.},
  doi = {10.1103/PhysRevE.76.036102},
  interhash = {a87821c7c8e7d5ca89cb369e6215a0f3},
  intrahash = {6145a42fe04aee556fa7a68c7cea7db3},
  journal = {Physical review. E, Statistical, nonlinear, and soft matter physics},
  number = {3 Pt 2},
  pages = 036102,
  publisher = {NIH Public Access},
  title = {Module identification in bipartite and directed networks},
  url = {http://arxiv.org/abs/physics/0701151},
  volume = 76,
  year = 2007
}