Collaboration graph

Last updated

In mathematics and social science, a collaboration graph [1] [2] is a graph modeling some social network where the vertices represent participants of that network (usually individual people) and where two distinct participants are joined by an edge whenever there is a collaborative relationship between them of a particular kind. Collaboration graphs are used to measure the closeness of collaborative relationships between the participants of the network.

Contents

Types considered in the literature

The most well-studied collaboration graphs include:

Features

By construction, the collaboration graph is a simple graph, since it has no loop-edges and no multiple edges. The collaboration graph need not be connected. Thus each person who never co-authored a joint paper represents an isolated vertex in the collaboration graph of mathematicians.

Both the collaboration graph of mathematicians and movie actors were shown to have "small world topology": they have a very large number of vertices, most of small degree, that are highly clustered, and a "giant" connected component with small average distances between vertices. [10]

Collaboration distance

The distance between two people/nodes in a collaboration graph is called the collaboration distance. [11] Thus the collaboration distance between two distinct nodes is equal to the smallest number of edges in an edge-path connecting them. If no path connecting two nodes in a collaboration graph exists, the collaboration distance between them is said to be infinite.

The collaboration distance may be used, for instance, for evaluating the citations of an author, a group of authors or a journal. [12]

In the collaboration graph of mathematicians, the collaboration distance from a particular person to Paul Erdős is called the Erdős number of that person. MathSciNet has a free online tool [13] for computing the collaboration distance between any two mathematicians as well as the Erdős number of a mathematician. This tool also shows the actual chain of co-authors that realizes the collaboration distance.

For the Hollywood graph, an analog of the Erdős number, called the Bacon number, has also been considered, which measures the collaboration distance to Kevin Bacon.

Generalizations

Some generalizations of the collaboration graph of mathematicians have also been considered. There is a hypergraph version, [14] where individual mathematicians are vertices and where a group of mathematicians (not necessarily just two) constitutes a hyperedge if there is a paper of which they were all co-authors. Another variation is a simple graph where two mathematicians are joined by an edge if and only if there is a paper with only two of them (and no others) as co-authors.[ citation needed ]

A multigraph version of a collaboration graph has also been considered where two mathematicians are joined by edges if they co-authored exactly papers together. Another variation is a weighted collaboration graph where with rational weights where two mathematicians are joined by an edge with weight whenever they co-authored exactly papers together. [15] This model naturally leads to the notion of a "rational Erdős number". [16]

See also

Related Research Articles

<span class="mw-page-title-main">Erdős number</span> Closeness of someones association with mathematician Paul Erdős

The Erdős number describes the "collaborative distance" between mathematician Paul Erdős and another person, as measured by authorship of mathematical papers. The same principle has been applied in other fields where a particular individual has collaborated with a large and broad number of peers.

<span class="mw-page-title-main">Graph theory</span> Area of discrete mathematics

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices which are connected by edges. A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics.

In combinatorics, Ramsey's theorem, in one of its graph-theoretic forms, states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph. To demonstrate the theorem for two colours (say, blue and red), let r and s be any two positive integers. Ramsey's theorem states that there exists a least positive integer R(r, s) for which every blue-red edge colouring of the complete graph on R(r, s) vertices contains a blue clique on r vertices or a red clique on s vertices. (Here R(r, s) signifies an integer that depends on both r and s.)

<span class="mw-page-title-main">Graph (discrete mathematics)</span> Vertices connected in pairs by edges

In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called vertices and each of the related pairs of vertices is called an edge. Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges. Graphs are one of the objects of study in discrete mathematics.

<span class="mw-page-title-main">Random graph</span> Graph generated by a random process

In mathematics, random graph is the general term to refer to probability distributions over graphs. Random graphs may be described simply by a probability distribution, or by a random process which generates them. The theory of random graphs lies at the intersection between graph theory and probability theory. From a mathematical perspective, random graphs are used to answer questions about the properties of typical graphs. Its practical applications are found in all areas in which complex networks need to be modeled – many random graph models are thus known, mirroring the diverse types of complex networks encountered in different areas. In a mathematical context, random graph refers almost exclusively to the Erdős–Rényi random graph model. In other contexts, any graph model may be referred to as a random graph.

<span class="mw-page-title-main">Vertex (graph theory)</span> Fundamental unit of which graphs are formed

In discrete mathematics, and more specifically in graph theory, a vertex or node is the fundamental unit of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges, while a directed graph consists of a set of vertices and a set of arcs. In a diagram of a graph, a vertex is usually represented by a circle with a label, and an edge is represented by a line or arrow extending from one vertex to another.

In the mathematical discipline of graph theory, the line graph of an undirected graph G is another graph L(G) that represents the adjacencies between edges of G. L(G) is constructed in the following way: for each edge in G, make a vertex in L(G); for every two edges in G that have a vertex in common, make an edge between their corresponding vertices in L(G).

<span class="mw-page-title-main">Degree (graph theory)</span> Number of edges touching a vertex in a graph

In graph theory, the degree of a vertex of a graph is the number of edges that are incident to the vertex; in a multigraph, a loop contributes 2 to a vertex's degree, for the two ends of the edge. The degree of a vertex is denoted or . The maximum degree of a graph , denoted by , and the minimum degree of a graph, denoted by , are the maximum and minimum of its vertices' degrees. In the multigraph shown on the right, the maximum degree is 5 and the minimum degree is 0.

<span class="mw-page-title-main">Wheel graph</span> Cycle graph plus universal vertex

In the mathematical discipline of graph theory, a wheel graph is a graph formed by connecting a single universal vertex to all vertices of a cycle. A wheel graph with n vertices can also be defined as the 1-skeleton of an (n – 1)-gonal pyramid. Some authors write Wn to denote a wheel graph with n vertices ; other authors instead use Wn to denote a wheel graph with n + 1 vertices, which is formed by connecting a single vertex to all vertices of a cycle of length n. The rest of this article uses the former notation.

<span class="mw-page-title-main">Frank Harary</span> American mathematician

Frank Harary was an American mathematician, who specialized in graph theory. He was widely recognized as one of the "fathers" of modern graph theory. Harary was a master of clear exposition and, together with his many doctoral students, he standardized the terminology of graphs. He broadened the reach of this field to include physics, psychology, sociology, and even anthropology. Gifted with a keen sense of humor, Harary challenged and entertained audiences at all levels of mathematical sophistication. A particular trick he employed was to turn theorems into games—for instance, students would try to add red edges to a graph on six vertices in order to create a red triangle, while another group of students tried to add edges to create a blue triangle. Because of the theorem on friends and strangers, one team or the other would have to win.

<span class="mw-page-title-main">Multigraph</span> Graph with multiple edges between two vertices

In mathematics, and more specifically in graph theory, a multigraph is a graph which is permitted to have multiple edges, that is, edges that have the same end nodes. Thus two vertices may be connected by more than one edge.

<span class="mw-page-title-main">Signed graph</span> Graph with sign-labeled edges

In the area of graph theory in mathematics, a signed graph is a graph in which each edge has a positive or negative sign.

<span class="mw-page-title-main">Hypercube graph</span> Graphs formed by a hypercubes edges and vertices

In graph theory, the hypercube graphQn is the graph formed from the vertices and edges of an n-dimensional hypercube. For instance, the cube graph Q3 is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. Qn has 2n vertices, 2n – 1n edges, and is a regular graph with n edges touching each vertex.

<span class="mw-page-title-main">Unit distance graph</span> Geometric graph with unit edge lengths

In mathematics, particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points whenever the distance between them is exactly one. To distinguish these graphs from a broader definition that allows some non-adjacent pairs of vertices to be at distance one, they may also be called strict unit distance graphs or faithful unit distance graphs. As a hereditary family of graphs, they can be characterized by forbidden induced subgraphs. The unit distance graphs include the cactus graphs, the matchstick graphs and penny graphs, and the hypercube graphs. The generalized Petersen graphs are non-strict unit distance graphs.

<span class="mw-page-title-main">Rado graph</span> Infinite graph containing all countable graphs

In the mathematical field of graph theory, the Rado graph, Erdős–Rényi graph, or random graph is a countably infinite graph that can be constructed by choosing independently at random for each pair of its vertices whether to connect the vertices by an edge. The names of this graph honor Richard Rado, Paul Erdős, and Alfréd Rényi, mathematicians who studied it in the early 1960s; it appears even earlier in the work of Wilhelm Ackermann (1937). The Rado graph can also be constructed non-randomly, by symmetrizing the membership relation of the hereditarily finite sets, by applying the BIT predicate to the binary representations of the natural numbers, or as an infinite Paley graph that has edges connecting pairs of prime numbers congruent to 1 mod 4 that are quadratic residues modulo each other.

<span class="mw-page-title-main">Erdős–Rényi model</span> Two closely related models for generating random graphs

In the mathematical field of graph theory, the Erdős–Rényi model refers to one of two closely related models for generating random graphs or the evolution of a random network. These models are named after Hungarian mathematicians Paul Erdős and Alfréd Rényi, who introduced one of the models in 1959. Edgar Gilbert introduced the other model contemporaneously and independently of Erdős and Rényi. In the model of Erdős and Rényi, all graphs on a fixed vertex set with a fixed number of edges are equally likely. In the model introduced by Gilbert, also called the Erdős–Rényi–Gilbert model, each edge has a fixed probability of being present or absent, independently of the other edges. These models can be used in the probabilistic method to prove the existence of graphs satisfying various properties, or to provide a rigorous definition of what it means for a property to hold for almost all graphs.

<span class="mw-page-title-main">Directed graph</span> Graph with oriented edges

In mathematics, and more specifically in graph theory, a directed graph is a graph that is made up of a set of vertices connected by directed edges, often called arcs.

In graph theory, the De Bruijn–Erdős theorem relates graph coloring of an infinite graph to the same problem on its finite subgraphs. It states that, when all finite subgraphs can be colored with colors, the same is true for the whole graph. The theorem was proved by Nicolaas Govert de Bruijn and Paul Erdős (1951), after whom it is named.

<span class="mw-page-title-main">Pancyclic graph</span>

In the mathematical study of graph theory, a pancyclic graph is a directed graph or undirected graph that contains cycles of all possible lengths from three up to the number of vertices in the graph. Pancyclic graphs are a generalization of Hamiltonian graphs, graphs which have a cycle of the maximum possible length.

<span class="mw-page-title-main">Dimension (graph theory)</span>

In mathematics, and particularly in graph theory, the dimension of a graph is the least integer n such that there exists a "classical representation" of the graph in the Euclidean space of dimension n with all the edges having unit length.

References

  1. ↑ Odda, Tom (1979). "On properties of a well-known graph or what is your Ramsey number? Topics in graph theory". Annals of the New York Academy of Sciences. New York, 1977: New York Academy of Sciences. 328: 166–172. doi:10.1111/j.1749-6632.1979.tb17777.x. S2CID   84887029.{{cite journal}}: CS1 maint: location (link)
  2. ↑ Frank Harary. Topics in Graph Theory. New York Academy of Sciences, 1979. ISBN   0-89766-028-5
  3. ↑ Vladimir Batagelj and Andrej Mrvar, Some analyses of Erdos collaboration graph. Social Networks, vol. 22 (2000), no. 2, pp. 173–186.
  4. ↑ Casper Goffman. And what is your Erdos number?, American Mathematical Monthly, vol. 76 (1979), p. 791
  5. ↑ Chaomei Chen, C. Chen. Mapping Scientific Frontiers: The Quest for Knowledge Visualization. Springer-Verlag New York. January 2003. ISBN   978-1-85233-494-9. See p. 94.
  6. ↑ Fan Chung, Linyuan Lu. Complex Graphs and Networks, Vol. 107. American Mathematical Society. October 2006. ISBN   978-0-8218-3657-6. See p. 16
  7. ↑ Albert-László Barabási and Réka Albert, Emergence of scaling in random networks. Science, vol. 286 (1999), no. 5439, pp. 509–512
  8. ↑ V. Boginski, S. Butenko, P.M. Pardalos, O. Prokopyev. Collaboration networks in sports. pp. 265–277. Economics, Management, and Optimization in Sports. Springer-Verlag, New York, February 2004. ISBN   978-3-540-20712-2
  9. ↑ Malbas, Vincent Schubert (2015). "Mapping the collaboration networks of biomedical research in Southeast Asia". PeerJ PrePrints. 3: e1160. doi: 10.7287/peerj.preprints.936v1 .
  10. ↑ Jerrold W. Grossman. The evolution of the mathematical research collaboration graph. Proceedings of the Thirty-Third Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 2002). Congressus Numerantium. Vol. 158 (2002), pp. 201–212.
  11. ↑ Deza, Elena; Deza, Michel-Marie (2006). "Ch. 22". Dictionary of Distances. Elsevier. p. 279. ISBN   978-0-444-52087-6..
  12. ↑ Bras-Amorós, M.; Domingo-Ferrer, J.; Torra, V. (2011). "A bibliometric index based on the collaboration distance between cited and citing authors". Journal of Informetrics. 5 (2): 248–264. doi:10.1016/j.joi.2010.11.001. hdl:10261/138172.
  13. ↑ MathSciNet Collaboration Distance Calculator. American Mathematical Society. Accessed May 23, 2008
  14. ↑ Frank Harary. Topics in Graph Theory. New York Academy of Sciences, 1979. ISBN   0-89766-028-5 See p. 166
  15. ↑ Mark E.J. Newman. Who Is the Best Connected Scientist? A Study of Scientific Coauthorship Networks. Lecture Notes in Physics, vol. 650, pp. 337–370. Springer-Verlag. Berlin. 2004. ISBN   978-3-540-22354-2.
  16. ↑ Alexandru T. Balaban and Douglas J. Klein.Co-authorship, rational Erdős numbers, and resistance distances in graphs. Scientometrics, vol. 55 (2002), no. 1, pp. 59–70.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.