Chayes, J. (2013),
'Mathematics of Web science: structure, dynamics and incentives', Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences
371
(1987)
.
[BibTeX]
[Endnote]
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.
Dorling, D.
(2012),
The Visualisation of Spatial Social Structure
, John Wiley & Sons
, Hoboken
.
[BibTeX]
[Endnote]
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.
Baur, M.; Gaertler, M.; Görke, R.; Krug, M. & Wagner, D. (2007),
Generating Graphs with Predefined k-Core Structure, in
'Proceedings of the European Conference of Complex Systems'
.
[BibTeX]
[Endnote]
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.
Brandes, U. & Lerner, J. (2007),
Role-equivalent Actors in Networks, in
Sergei Obiedkov & Camille Roth, ed.,
'ICFCA 2007 Satellite Workshop on Social Network Analysis and Conceptual Structures: Exploring Opportunities'
.
[BibTeX]
[Endnote]
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.
Newman, M. E. J. (2006),
'Modularity and community structure in networks', Proceedings of the National Academy of Sciences
103
(23)
, 8577--8582
.
[BibTeX]
[Endnote]
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.
Golder, S. & Huberman, B. A. (2005),
'The Structure of Collaborative Tagging Systems'
, Technical report, Information Dynamics Lab, HP Labs
.
[BibTeX]
[Endnote]
Jäschke, R. (2005),
'Die Struktur der Monoide binärer Relationen auf endlichen Mengen', Master's thesis, Technische Universität Dresden.
[BibTeX]
[Endnote]
Brandes, U. & Lerner, J. (2004),
Structural Similarity in Graphs (A Relaxation Approach for Role Assignment)., in
Rudolf Fleischer & Gerhard Trippen, ed.,
'ISAAC'
, Springer,
, pp. 184-195
.
[BibTeX]
[Endnote]
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.
Clauset, A.; Newman, M. & Moore, C. (2004),
'Finding community structure in very large networks', Physical Review E
70
, 066111
.
[BibTeX]
[Endnote]
Kumar, R.; Novak, J.; Raghavan, P. & Tomkins, A. (2004),
'Structure and evolution of blogspace', Commun. ACM
47
(12)
, 35--39
.
[BibTeX]
[Endnote]
Newman, M. & Girvan, M. (2004),
'Finding and evaluating community structure in networks', Physical Review E
69
, 026113
.
[BibTeX]
[Endnote]
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.
Tyler, J. R.; Wilkinson, D. M. & Huberman, B. A.
(2003), Email as Spectroscopy: Automated Discovery of Community Structure within Organizations
, Kluwer, B.V.
, Deventer, The Netherlands, The Netherlands
, pp. 81--96
.
[BibTeX]
[Endnote]
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.
Girvan, M. & Newman, M. (2002),
'Community structure in social and biological networks', Proceedings of the National Academy of Science
99
(12)
, 7821-7826
.
[BibTeX]
[Endnote]
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.
Wille, R. & Wille, U. (1996),
'Coordinatization of ordinal structures', Order
13
(3)
, 281--294
.
[BibTeX]
[Endnote]
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 -
White, H. D. & Griffith, B. C. (1981),
'Author cocitation: A literature measure of intellectual structure', Journal of the American Society for Information Science
32
(3)
, 163--171
.
[BibTeX]
[Endnote]
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.