Dr Chayes’ talk described how, to a discrete mathematician, ‘all the world’s a graph, and all the people and domains merely vertices’. A graph is represented as a set of vertices V and a set of edges E, so that, for instance, in the World Wide Web, V is the set of pages and E the directed hyperlinks; in a social network, V is the people and E the set of relationships; and in the autonomous system Internet, V is the set of autonomous systems (such as AOL, Yahoo! and MSN) and E the set of connections. This means that mathematics can be used to study the Web (and other large graphs in the online world) in the following way: first, we can model online networks as large finite graphs; second, we can sample pieces of these graphs; third, we can understand and then control processes on these graphs; and fourth, we can develop algorithms for these graphs and apply them to improve the online experience.

@article{chayes2013mathematics, author = {Chayes, Jennifer}, title = {Mathematics of Web science: structure, dynamics and incentives}, journal = {Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences}, year = {2013}, volume = {371}, number = {1987}, url = {http://rsta.royalsocietypublishing.org/content/371/1987/20120377.abstract}, doi = {10.1098/rsta.2012.0377}, keywords = {dynamics, incentive, math, structure, webscience}, abstract = {Dr Chayes’ talk described how, to a discrete mathematician, ‘all the world’s a graph, and all the people and domains merely vertices’. A graph is represented as a set of vertices V and a set of edges E, so that, for instance, in the World Wide Web, V is the set of pages and E the directed hyperlinks; in a social network, V is the people and E the set of relationships; and in the autonomous system Internet, V is the set of autonomous systems (such as AOL, Yahoo! and MSN) and E the set of connections. This means that mathematics can be used to study the Web (and other large graphs in the online world) in the following way: first, we can model online networks as large finite graphs; second, we can sample pieces of these graphs; third, we can understand and then control processes on these graphs; and fourth, we can develop algorithms for these graphs and apply them to improve the online experience.} }

%0 = article %A = Chayes, Jennifer %D = 2013 %T = Mathematics of Web science: structure, dynamics and incentives %U = http://rsta.royalsocietypublishing.org/content/371/1987/20120377.abstract

How do you draw a map of 100,000 places, of more than a million flows of people, of changes over time and space, of different kinds of spaces, surfaces and volumes, from human travel time to landscapes of hopes, fears, migration, manufacturing and mortality? How do you turn the millions of numbers concerning some of the most important moments of our lives into images that allow us to appreciate the aggregate while still remembering the detail? The visualization of spatial social structure means, literally, making visible the geographical patterns to the way our lives have come to be s.

@book{dorling2012visualisation, author = {Dorling, Danny}, title = {The Visualisation of Spatial Social Structure}, series = {Wiley Series in Computational and Quantitative Social Science}, publisher = {John Wiley & Sons}, address = {Hoboken}, year = {2012}, edition = {2nd}, url = {http://public.eblib.com/EBLPublic/PublicView.do?ptiID=945112}, isbn = {9781118354001 1118354001}, keywords = {geography, gis, information, social, spatial, stair, structure, system}, abstract = {How do you draw a map of 100,000 places, of more than a million flows of people, of changes over time and space, of different kinds of spaces, surfaces and volumes, from human travel time to landscapes of hopes, fears, migration, manufacturing and mortality? How do you turn the millions of numbers concerning some of the most important moments of our lives into images that allow us to appreciate the aggregate while still remembering the detail? The visualization of spatial social structure means, literally, making visible the geographical patterns to the way our lives have come to be s.} }

%0 = book %A = Dorling, Danny %C = Hoboken %D = 2012 %I = John Wiley & Sons %T = The Visualisation of Spatial Social Structure %U = http://public.eblib.com/EBLPublic/PublicView.do?ptiID=945112

The modeling of realistic networks is of great importance for modern complex systems research. Previous procedures typically model the natural growth of networks by means of iteratively adding nodes, geometric positioning information, a definition of link connectivity based on the preference for nearest neighbors or already highly connected nodes, or combine several of these approaches. Our novel model is based on the well-know concept of k-cores, originally introduced in social network analysis. Recent studies exposed the significant k-core structure of several real world systems, e.g. the AS network of the Internet. We present a simple and efficient method for generating networks which strictly adhere to the characteristics of a given k-core structure, called core fingerprint. We show-case our algorithm in a comparative evaluation with two well-known AS network generators.

@inproceedings{baur2007generating, author = {Baur, Michael and Gaertler, Marco and Görke, Robert and Krug, Marcus and Wagner, Dorothea}, title = {Generating Graphs with Predefined k-Core Structure}, booktitle = {Proceedings of the European Conference of Complex Systems}, year = {2007}, url = {http://i11www.ira.uka.de/extra/publications/bggkw-ggpcs-07.pdf}, keywords = {analysis, core, generator, graph, structure}, abstract = {The modeling of realistic networks is of great importance for modern complex systems research. Previous procedures typically model the natural growth of networks by means of iteratively adding nodes, geometric positioning information, a definition of link connectivity based on the preference for nearest neighbors or already highly connected nodes, or combine several of these approaches. Our novel model is based on the well-know concept of k-cores, originally introduced in social network analysis. Recent studies exposed the significant k-core structure of several real world systems, e.g. the AS network of the Internet. We present a simple and efficient method for generating networks which strictly adhere to the characteristics of a given k-core structure, called core fingerprint. We show-case our algorithm in a comparative evaluation with two well-known AS network generators. } }

%0 = inproceedings %A = Baur, Michael and Gaertler, Marco and Görke, Robert and Krug, Marcus and Wagner, Dorothea %B = Proceedings of the European Conference of Complex Systems %D = 2007 %T = Generating Graphs with Predefined k-Core Structure %U = http://i11www.ira.uka.de/extra/publications/bggkw-ggpcs-07.pdf

Abstract. Communities in social networks are often defined as groups of densely connected actors. However, members of the same dense group are not equal but may differ largely in their social position or in the role they play. Furthermore, the same positions can be found across the borders of dense communities so that networks contain a significant group structure which does not coincide with the structure of dense groups. This papers gives a survey over formalizations of network-positions with a special emphasis on the use of algebraic notions.

@inproceedings{Brandes07Role, author = {Brandes, Ulrik and Lerner, Jürgen}, title = {Role-equivalent Actors in Networks}, editor = {Obiedkov, Sergei and Roth, Camille}, booktitle = {ICFCA 2007 Satellite Workshop on Social Network Analysis and Conceptual Structures: Exploring Opportunities}, year = {2007}, url = {http://www.inf.uni-konstanz.de/algo/publications/bl-rean-07.pdf}, keywords = {actor, role, seminar2009, structure, sna, analysis, network, social}, abstract = {Abstract. Communities in social networks are often defined as groups of densely connected actors. However, members of the same dense group are not equal but may differ largely in their social position or in the role they play. Furthermore, the same positions can be found across the borders of dense communities so that networks contain a significant group structure which does not coincide with the structure of dense groups. This papers gives a survey over formalizations of network-positions with a special emphasis on the use of algebraic notions.} }

%0 = inproceedings %A = Brandes, Ulrik and Lerner, Jürgen %B = ICFCA 2007 Satellite Workshop on Social Network Analysis and Conceptual Structures: Exploring Opportunities %D = 2007 %T = Role-equivalent Actors in Networks %U = http://www.inf.uni-konstanz.de/algo/publications/bl-rean-07.pdf

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.

@article{newman2006modularity, author = {Newman, M. E. J.}, title = {Modularity and community structure in networks}, journal = {Proceedings of the National Academy of Sciences}, year = {2006}, volume = {103}, number = {23}, pages = {8577--8582}, doi = {10.1073/pnas.0601602103}, keywords = {clustering, community, graph, modularity, network, structure}, 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.} }

%0 = article %A = Newman, M. E. J. %D = 2006 %T = Modularity and community structure in networks

@techreport{GH05structure, author = {Golder, Scott and Huberman, Bernardo A.}, title = {The Structure of Collaborative Tagging Systems}, year = {2005}, url = {http://arxiv.org/abs/cs.DL/0508082}, keywords = {folksonomy, tagging, structure} }

%0 = techreport %A = Golder, Scott and Huberman, Bernardo A. %B = } %C = %D = 2005 %I = %T = The Structure of Collaborative Tagging Systems} %U = http://arxiv.org/abs/cs.DL/0508082

@mastersthesis{jaeschke2005struktur, author = {Jäschke, Robert}, title = {Die Struktur der Monoide binärer Relationen auf endlichen Mengen}, school = {Technische Universität Dresden}, type = {Diplomarbeit}, year = {2005}, url = {http://www.kde.cs.uni-kassel.de/pub/pdf/jaeschke2005struktur.pdf}, keywords = {2005, binary, diploma, monoid, myown, relation, semigroup, structure, thesis} }

%0 = mastersthesis %A = Jäschke, Robert %D = 2005 %T = Die Struktur der Monoide binärer Relationen auf endlichen Mengen %U = http://www.kde.cs.uni-kassel.de/pub/pdf/jaeschke2005struktur.pdf

Standard methods for role assignment partition the vertex set of a graph in such a way that vertices in the same class can be considered to have equivalent roles in the graph. Several classes of equivalence relations such as regular equivalence and equitable partitions have been proposed for role assignment, but they all suffer from the strictness of classifying vertices into being either equivalent or not. It is an open problem how to allow for varying degrees of similarity. Proposals include ad-hoc algorithmic approaches and optimization approaches which are computationally hard. In this paper we introduce the concept of structural similarity by relaxation of equitable partitions, thus providing a theoretical foundation for similarity measures which enjoys desirable properties with respect to existence, structure, and tractability.

@inproceedings{conf/isaac/BrandesL04, author = {Brandes, Ulrik and Lerner, Jürgen}, title = {Structural Similarity in Graphs (A Relaxation Approach for Role Assignment).}, editor = {Fleischer, Rudolf and Trippen, Gerhard}, booktitle = {ISAAC}, series = {Lecture Notes in Computer Science}, publisher = {Springer}, year = {2004}, volume = {3341}, pages = {184-195}, url = {http://kops.ub.uni-konstanz.de/volltexte/2009/7777/}, isbn = {3-540-24131-0}, keywords = {actor, assignment, graph, relaxation, role, similarity, structure}, abstract = {Standard methods for role assignment partition the vertex set of a graph in such a way that vertices in the same class can be considered to have equivalent roles in the graph. Several classes of equivalence relations such as regular equivalence and equitable partitions have been proposed for role assignment, but they all suffer from the strictness of classifying vertices into being either equivalent or not. It is an open problem how to allow for varying degrees of similarity. Proposals include ad-hoc algorithmic approaches and optimization approaches which are computationally hard. In this paper we introduce the concept of structural similarity by relaxation of equitable partitions, thus providing a theoretical foundation for similarity measures which enjoys desirable properties with respect to existence, structure, and tractability.} }

%0 = inproceedings %A = Brandes, Ulrik and Lerner, Jürgen %B = ISAAC %D = 2004 %I = Springer %T = Structural Similarity in Graphs (A Relaxation Approach for Role Assignment). %U = http://kops.ub.uni-konstanz.de/volltexte/2009/7777/

@article{clauset-2004-70, author = {Clauset, Aaron and Newman, M.E.J. and Moore, Cristopher}, title = {Finding community structure in very large networks}, journal = {Physical Review E}, year = {2004}, volume = {70}, pages = {066111}, url = {http://www.citebase.org/cgi-bin/citations?id=oai:arXiv.org:cond-mat/0408187}, keywords = {community, detection, gn, large, network, newman, structure} }

%0 = article %A = Clauset, Aaron and Newman, M.E.J. and Moore, Cristopher %D = 2004 %T = Finding community structure in very large networks %U = http://www.citebase.org/cgi-bin/citations?id=oai:arXiv.org:cond-mat/0408187

@article{1035162, author = {Kumar, Ravi and Novak, Jasmine and Raghavan, Prabhakar and Tomkins, Andrew}, title = {Structure and evolution of blogspace}, journal = {Commun. ACM}, publisher = {ACM Press}, address = {New York, NY, USA}, year = {2004}, volume = {47}, number = {12}, pages = {35--39}, url = {http://doi.acm.org/10.1145/1035134.1035162}, issn = {0001-0782}, keywords = {blogging, seminar2006, structure, community} }

%0 = article %A = Kumar, Ravi and Novak, Jasmine and Raghavan, Prabhakar and Tomkins, Andrew %C = New York, NY, USA %D = 2004 %I = ACM Press %T = Structure and evolution of blogspace %U = http://doi.acm.org/10.1145/1035134.1035162

We propose and study a set of algorithms for discovering community structure in networks - natural divisions of network nodes into densely connected subgroups. Our algorithms all share two definitive features: first, they involve iterative removal of edges from the network to split it into communities, the edges removed being identified using one of a number of possible "betweenness" measures, and second, these measures are, crucially, recalculated after each removal. We also propose a measure for the strength of the community structure found by our algorithms, which gives us an objective metric for choosing the number of communities into which a network should be divided. We demonstrate that our algorithms are highly effective at discovering community structure in both computer-generated and real-world network data, and show how they can be used to shed light on the sometimes dauntingly complex structure of networked systems.

@article{newman2004finding, author = {Newman, M.E.J. and Girvan, M.}, title = {Finding and evaluating community structure in networks}, journal = {Physical Review E}, year = {2004}, volume = {69}, pages = {026113}, url = {http://arxiv.org/abs/cond-mat/0308217}, doi = {10.1103/PhysRevE.69.026113}, keywords = {community, detection, girvan, gn, modularity, network, newman, structure}, abstract = {We propose and study a set of algorithms for discovering community structure in networks -- natural divisions of network nodes into densely connected subgroups. Our algorithms all share two definitive features: first, they involve iterative removal of edges from the network to split it into communities, the edges removed being identified using one of a number of possible "betweenness" measures, and second, these measures are, crucially, recalculated after each removal. We also propose a measure for the strength of the community structure found by our algorithms, which gives us an objective metric for choosing the number of communities into which a network should be divided. We demonstrate that our algorithms are highly effective at discovering community structure in both computer-generated and real-world network data, and show how they can be used to shed light on the sometimes dauntingly complex structure of networked systems. } }

%0 = article %A = Newman, M.E.J. and Girvan, M. %D = 2004 %T = Finding and evaluating community structure in networks %U = http://arxiv.org/abs/cond-mat/0308217

We describe a method for the automatic identification of communities of practice from email logs within an organization. We use a betweenness centrality algorithm that can rapidly find communities within a graph representing information flows. We apply this algorithm to an email corpus of nearly one million messages collected over a two-month span, and show that the method is effective at identifying true communities, both formal and informal, within these scale-free graphs. This approach also enables the identification of leadership roles within the communities. These studies are complemented by a qualitative evaluation of the results in the field.

@inbook{tyler2003email, author = {Tyler, Joshua R. and Wilkinson, Dennis M. and Huberman, Bernardo A.}, title = {Email as Spectroscopy: Automated Discovery of Community Structure within Organizations}, booktitle = {Communities and technologies}, publisher = {Kluwer, B.V.}, address = {Deventer, The Netherlands, The Netherlands}, year = {2003}, pages = {81--96}, url = {http://www.citebase.org/cgi-bin/citations?id=oai:arXiv.org:cond-mat/0303264}, keywords = {gn, detection, email, structure, community}, abstract = {We describe a method for the automatic identification of communities of practice from email logs within an organization. We use a betweenness centrality algorithm that can rapidly find communities within a graph representing information flows. We apply this algorithm to an email corpus of nearly one million messages collected over a two-month span, and show that the method is effective at identifying true communities, both formal and informal, within these scale-free graphs. This approach also enables the identification of leadership roles within the communities. These studies are complemented by a qualitative evaluation of the results in the field.} }

%0 = inbook %A = Tyler, Joshua R. and Wilkinson, Dennis M. and Huberman, Bernardo A. %B = Communities and technologies} %C = Deventer, The Netherlands, The Netherlands %D = 2003 %I = Kluwer, B.V. %T = Email as Spectroscopy: Automated Discovery of Community Structure within Organizations} %U = http://www.citebase.org/cgi-bin/citations?id=oai:arXiv.org:cond-mat/0303264

A number of recent studies have focused on the statistical properties of networked systems such as social networks and the Worldwide Web. Researchers have concentrated particularly on a few properties that seem to be common to many networks: the small-world property, power-law degree distributions, and network transitivity. In this article, we highlight another property that is found in many networks, the property of community structure, in which network nodes are joined together in tightly knit groups, between which there are only looser connections. We propose a method for detecting such communities, built around the idea of using centrality indices to find community boundaries. We test our method on computer-generated and real-world graphs whose community structure is already known and find that the method detects this known structure with high sensitivity and reliability. We also apply the method to two networks whose community structure is not well known--a collaboration network and a food web--and find that it detects significant and informative community divisions in both cases.

@article{gn02community, author = {Girvan, Michelle and Newman, M.E.J.}, title = {Community structure in social and biological networks}, journal = {Proceedings of the National Academy of Science}, year = {2002}, volume = {99}, number = {12}, pages = {7821-7826}, keywords = {social, gn, detection, structure, community, network}, abstract = {A number of recent studies have focused on the statistical properties of networked systems such as social networks and the Worldwide Web. Researchers have concentrated particularly on a few properties that seem to be common to many networks: the small-world property, power-law degree distributions, and network transitivity. In this article, we highlight another property that is found in many networks, the property of community structure, in which network nodes are joined together in tightly knit groups, between which there are only looser connections. We propose a method for detecting such communities, built around the idea of using centrality indices to find community boundaries. We test our method on computer-generated and real-world graphs whose community structure is already known and find that the method detects this known structure with high sensitivity and reliability. We also apply the method to two networks whose community structure is not well known---a collaboration network and a food web---and find that it detects significant and informative community divisions in both cases.} }

%0 = article %A = Girvan, Michelle and Newman, M.E.J. %D = 2002 %T = Community structure in social and biological networks

Dependencies between attributes in ordinal data contexts are algebraically described. Suitable conditions are analysed which allow coordinatizations of ordinal contexts (ordinal structures) by ordered n-quasigroups, ordered abelian groups, and ordered fields. The presented development offers a new approach to conjoint measurement.
-

@article{Wille96Coordinatization, author = {Wille, Rudolf and Wille, Uta}, title = {Coordinatization of ordinal structures}, journal = {Order}, year = {1996}, volume = {13}, number = {3}, pages = {281--294}, url = {http://dx.doi.org/10.1007/BF00338747}, keywords = {algebra, order, ordinal, structure}, abstract = {Dependencies between attributes in ordinal data contexts are algebraically described. Suitable conditions are analysed which allow coordinatizations of ordinal contexts (ordinal structures) by ordered n-quasigroups, ordered abelian groups, and ordered fields. The presented development offers a new approach to conjoint measurement. ER -} }

%0 = article %A = Wille, Rudolf and Wille, Uta %D = 1996 %T = Coordinatization of ordinal structures %U = http://dx.doi.org/10.1007/BF00338747

It is shown that the mapping of a particular area of science, in this case information science, can be done using authors as units of analysis and the cocitations of pairs of authors as the variable that indicates their “distances” from each other. The analysis assumes that the more two authors are cited together, the closer the relationship between them. The raw data are cocitation counts drawn online from Social Scisearch (Social Sciences Citation Index) over the period 1972–1979. The resulting map shows (1) identifiable author groups (akin to “schools”) of information science, (2) locations of these groups with respect to each other, (3) the degree of centrality and peripherality of authors within groups, (4) proximities of authors within group and across group boundaries (“border authors” who seem to connect various areas of research), and (5) positions of authors with respect to the map's axes, which were arbitrarily set spanning the most divergent groups in order to aid interpretation. Cocitation analysis of authors offers a new technique that might contribute to the understanding of intellectual structure in the sciences and possibly in other areas to the extent that those areas rely on serial publications. The technique establishes authors, as well as documents, as an effective unit in analyzing subject specialties.

@article{white1981author, author = {White, Howard D. and Griffith, Belver C.}, title = {Author cocitation: A literature measure of intellectual structure}, journal = {Journal of the American Society for Information Science}, publisher = {Wiley}, year = {1981}, volume = {32}, number = {3}, pages = {163--171}, url = {http://dx.doi.org/10.1002/asi.4630320302}, doi = {10.1002/asi.4630320302}, issn = {1097-4571}, keywords = {analysis, citation, literature, structure}, abstract = {It is shown that the mapping of a particular area of science, in this case information science, can be done using authors as units of analysis and the cocitations of pairs of authors as the variable that indicates their “distances” from each other. The analysis assumes that the more two authors are cited together, the closer the relationship between them. The raw data are cocitation counts drawn online from Social Scisearch (Social Sciences Citation Index) over the period 1972–1979. The resulting map shows (1) identifiable author groups (akin to “schools”) of information science, (2) locations of these groups with respect to each other, (3) the degree of centrality and peripherality of authors within groups, (4) proximities of authors within group and across group boundaries (“border authors” who seem to connect various areas of research), and (5) positions of authors with respect to the map's axes, which were arbitrarily set spanning the most divergent groups in order to aid interpretation. Cocitation analysis of authors offers a new technique that might contribute to the understanding of intellectual structure in the sciences and possibly in other areas to the extent that those areas rely on serial publications. The technique establishes authors, as well as documents, as an effective unit in analyzing subject specialties.} }

%0 = article %A = White, Howard D. and Griffith, Belver C. %D = 1981 %I = Wiley %T = Author cocitation: A literature measure of intellectual structure %U = http://dx.doi.org/10.1002/asi.4630320302