Triadic closure

Last updated
A diagram demonstrating the principle of triadic closure. If A is linked to B, and A is also linked to C, then there is a tendency for B to become linked to C. Triadic closure.svg
A diagram demonstrating the principle of triadic closure. If A is linked to B, and A is also linked to C, then there is a tendency for B to become linked to C.

Triadic closure is a concept in social network theory, first suggested by German sociologist Georg Simmel in his 1908 book Soziologie [Sociology: Investigations on the Forms of Sociation]. [1] Triadic closure is the property among three nodes A, B, and C (representing people, for instance), that if the connections A-B and A-C exist, there is a tendency for the new connection B-C to be formed. [2] Triadic closure can be used to understand and predict the growth of networks, although it is only one of many mechanisms by which new connections are formed in complex networks. [3]

Contents

History

Triadic closure was made popular by Mark Granovetter in his 1973 article The Strength of Weak Ties. [4] There he synthesized the theory of cognitive balance first introduced by Fritz Heider in 1946 with a Simmelian understanding of social networks. In general terms, cognitive balance refers to the propensity of two individuals to want to feel the same way about an object. If the triad of three individuals is not closed, then the person connected to both of the individuals will want to close this triad in order to achieve closure in the relationship network.

Measurements

The two most common measures of triadic closure for a graph are (in no particular order) the clustering coefficient and transitivity for that graph.

Clustering coefficient

One measure for the presence of triadic closure is clustering coefficient, as follows:

Let be an undirected simple graph (i.e., a graph having no self-loops or multiple edges) with V the set of vertices and E the set of edges. Also, let and denote the number of vertices and edges in G, respectively, and let be the degree of vertex i.

We can define a triangle among the triple of vertices , , and to be a set with the following three edges: {(i,j), (j,k), (i,k)}.

We can also define the number of triangles that vertex is involved in as and, as each triangle is counted three times, we can express the number of triangles in G as .

Assuming that triadic closure holds, only two strong edges are required for a triple to form. Thus, the number of theoretical triples that should be present under the triadic closure hypothesis for a vertex is , assuming . We can express .

Now, for a vertex with , the clustering coefficient of vertex is the fraction of triples for vertex that are closed, and can be measured as . Thus, the clustering coefficient of graph is given by , where is the number of nodes with degree at least 2.

Transitivity

Another measure for the presence of triadic closure is transitivity, defined as .

Causes and effects

In a trust network, triadic closure is likely to develop due to the transitive property. If a node A trusts node B, and node B trusts node C, node A will have the basis to trust node C. In a social network, strong triadic closure occurs because there is increased opportunity for nodes A and C with common neighbor B to meet and therefore create at least weak ties. Node B also has the incentive to bring A and C together to decrease the latent stress in two separate relationships. [3]

Networks that stay true to this principle become highly interconnected and have very high clustering coefficients. However, networks that do not follow this principle turn out to be poorly connected and may suffer from instability once negative relations are included.

Triadic closure is a good model for how networks will evolve over time. While simple graph theory tends to analyze networks at one point in time, applying the triadic closure principle can predict the development of ties within a network and show the progression of connectivity. [3]

In social networks, triadic closure facilitates cooperative behavior, but when new connections are made via referrals from existing connections the average global fraction of cooperators is less than when individuals choose new connections randomly from the population at large. Two possible effects of these are by the structural and informational construction. The structural construction arises from the propensity toward high clusterability. The informational construction comes from the assumption that an individual knows something about a friend's friend, as opposed to a random stranger.

Strong Triadic Closure Property and local bridges

A node A with strong ties to two neighbors B and C obeys the Strong Triadic Closure Property if these neighbors have an edge (either a weak or strong tie) between them. [3]

Related Research Articles

<span class="mw-page-title-main">Scale-free network</span> Network whose degree distribution follows a power law

A scale-free network is a network whose degree distribution follows a power law, at least asymptotically. That is, the fraction P(k) of nodes in the network having k connections to other nodes goes for large values of k as

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

<span class="mw-page-title-main">Edge coloring</span> Problem of coloring a graphs edges such that meeting edges do not match

In graph theory, a proper edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most k different colors, for a given value of k, or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.

<span class="mw-page-title-main">Dirac comb</span> Periodic distribution ("function") of "point-mass" Dirac delta sampling

In mathematics, a Dirac comb is a periodic function with the formula

In graph theory, a clustering coefficient is a measure of the degree to which nodes in a graph tend to cluster together. Evidence suggests that in most real-world networks, and in particular social networks, nodes tend to create tightly knit groups characterised by a relatively high density of ties; this likelihood tends to be greater than the average probability of a tie randomly established between two nodes.

<span class="mw-page-title-main">Centrality</span> Degree of connectedness within a graph

In graph theory and network analysis, indicators of centrality assign numbers or rankings to nodes within a graph corresponding to their network position. Applications include identifying the most influential person(s) in a social network, key infrastructure nodes in the Internet or urban networks, super-spreaders of disease, and brain networks. Centrality concepts were first developed in social network analysis, and many of the terms used to measure centrality reflect their sociological origin.

<span class="mw-page-title-main">Maximal independent set</span> Independent set which is not a subset of any other independent set

In graph theory, a maximal independent set (MIS) or maximal stable set is an independent set that is not a subset of any other independent set. In other words, there is no vertex outside the independent set that may join it because it is maximal with respect to the independent set property.

<span class="mw-page-title-main">Schwarz triangle</span> Spherical triangle that can be used to tile a sphere

In geometry, a Schwarz triangle, named after Hermann Schwarz, is a spherical triangle that can be used to tile a sphere, possibly overlapping, through reflections in its edges. They were classified in Schwarz (1873).

In statistics, the Kendall rank correlation coefficient, commonly referred to as Kendall's τ coefficient, is a statistic used to measure the ordinal association between two measured quantities. A τ test is a non-parametric hypothesis test for statistical dependence based on the τ coefficient. It is a measure of rank correlation: the similarity of the orderings of the data when ranked by each of the quantities. It is named after Maurice Kendall, who developed it in 1938, though Gustav Fechner had proposed a similar measure in the context of time series in 1897.

<span class="mw-page-title-main">Watts–Strogatz model</span> Method of generating random small-world graphs

The Watts–Strogatz model is a random graph generation model that produces graphs with small-world properties, including short average path lengths and high clustering. It was proposed by Duncan J. Watts and Steven Strogatz in their article published in 1998 in the Nature scientific journal. The model also became known as the (Watts) beta model after Watts used to formulate it in his popular science book Six Degrees.

Stress majorization is an optimization strategy used in multidimensional scaling (MDS) where, for a set of -dimensional data items, a configuration of points in -dimensional space is sought that minimizes the so-called stress function . Usually is or , i.e. the matrix lists points in or dimensional Euclidean space so that the result may be visualised. The function is a cost or loss function that measures the squared differences between ideal distances and actual distances in r-dimensional space. It is defined as:

In mathematics and physics, a quantum graph is a linear, network-shaped structure of vertices connected on edges in which each edge is given a length and where a differential equation is posed on each edge. An example would be a power network consisting of power lines (edges) connected at transformer stations (vertices); the differential equations would then describe the voltage along each of the lines, with boundary conditions for each edge provided at the adjacent vertices ensuring that the current added over all edges adds to zero at each vertex.

FD-DEVS is a formalism for modeling and analyzing discrete event dynamic systems in both simulation and verification ways. FD-DEVS also provides modular and hierarchical modeling features which have been inherited from Classic DEVS.

<span class="mw-page-title-main">Conductance (graph theory)</span> A mixing property of Markov chains and graphs

In theoretical computer science, graph theory, and mathematics, the conductance is a parameter of a Markov chain that is closely tied to its mixing time, that is, how rapidly the chain converges to its stationary distribution, should it exist. Equivalently, the conductance can be viewed as a parameter of a directed graph, in which case it can be used to analyze how quickly random walks in the graph converge.

<span class="mw-page-title-main">Network science</span> Academic field

Network science is an academic field which studies complex networks such as telecommunication networks, computer networks, biological networks, cognitive and semantic networks, and social networks, considering distinct elements or actors represented by nodes and the connections between the elements or actors as links. The field draws on theories and methods including graph theory from mathematics, statistical mechanics from physics, data mining and information visualization from computer science, inferential modeling from statistics, and social structure from sociology. The United States National Research Council defines network science as "the study of network representations of physical, biological, and social phenomena leading to predictive models of these phenomena."

In coding theory, Zemor's algorithm, designed and developed by Gilles Zemor, is a recursive low-complexity approach to code construction. It is an improvement over the algorithm of Sipser and Spielman.

<span class="mw-page-title-main">Configuration model</span>

In network science, the configuration model is a method for generating random networks from a given degree sequence. It is widely used as a reference model for real-life social networks, because it allows the modeler to incorporate arbitrary degree distributions.

A central problem in algorithmic graph theory is the shortest path problem. One of the generalizations of the shortest path problem is known as the single-source-shortest-paths (SSSP) problem, which consists of finding the shortest paths from a source vertex to all other vertices in the graph. There are classical sequential algorithms which solve this problem, such as Dijkstra's algorithm. In this article, however, we present two parallel algorithms solving this problem.

The mixed Chinese postman problem (MCPP or MCP) is the search for the shortest traversal of a graph with a set of vertices V, a set of undirected edges E with positive rational weights, and a set of directed arcs A with positive rational weights that covers each edge or arc at least once at minimal cost. The problem has been proven to be NP-complete by Papadimitriou. The mixed Chinese postman problem often arises in arc routing problems such as snow ploughing, where some streets are too narrow to traverse in both directions while other streets are bidirectional and can be plowed in both directions. It is easy to check if a mixed graph has a postman tour of any size by verifying if the graph is strongly connected. The problem is NP hard if we restrict the postman tour to traverse each arc exactly once or if we restrict it to traverse each edge exactly once, as proved by Zaragoza Martinez.

<span class="mw-page-title-main">Brandes' algorithm</span> Algorithm for finding important nodes in a graph

In network theory, Brandes' algorithm is an algorithm for calculating the betweenness centrality of vertices in a graph. The algorithm was first published in 2001 by Ulrik Brandes. Betweenness centrality, along with other measures of centrality, is an important measure in many real-world networks, such as social networks and computer networks.

References

  1. Georg Simmel Archived 2021-10-07 at the Wayback Machine , originator of the concept: "Facebook" article at the New York Times website. Retrieved on December 21, 2007.
  2. Working concept Archived 2018-10-20 at the Wayback Machine of triadic closure: book review of Duncan Watts' "Six Degrees: The Science of a Connected Age" at the Serendip (Bryn Mawr College) website. Retrieved on December 21, 2007.
  3. 1 2 3 4 Easley, David; Kleinberg, Jon (2010). Networks, crowds, and markets: reasoning about a highly connected world. Cambridge: Cambridge University Press. ISBN   978-0-521-19533-1.
  4. Granovetter, M. (1973). "The Strength of Weak Ties Archived 2008-02-16 at the Wayback Machine ", American Journal of Sociology, Vol. 78, Issue 6, May 1360-80.