Contents 1 History 2 Measurements 2.1 Clustering coefficient 2.2 Transitivity 3 Causes and effects 4 Strong Triadic Closure Property and local bridges 4.1 Proof by contradiction 5 References History[edit]
This section does not cite any sources. Please help improve this section by adding citations to reliable sources. Unsourced material may be challenged and removed. (September 2009) (Learn how and when to remove this template message) 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[edit] One measure for the presence of triadic closure is clustering coefficient, as follows: Let G = ( V , E ) displaystyle G=(V,E) 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 N =
V
displaystyle N=V and M =
E
displaystyle M=E denote the number of vertices and edges in G, respectively, and let d i displaystyle d_ i be the degree of vertex i. Then we can define a triangle among the triple of vertices i displaystyle i , j displaystyle j , and k displaystyle k to be a set with the following three edges: (i,j), (j,k), (i,k) . Then we can define the number of triangles that vertex i displaystyle i is involved in as δ ( i ) displaystyle delta (i) and, as each triangle is counted three times, we can express the number of triangles in G as δ ( G ) = 1 3 ∑ i ∈ V δ ( i ) displaystyle delta (G)= frac 1 3 sum _ iin V delta (i) . Assuming that triadic closure holds, only two strong edges are required for a triple to form and the number of triples of vertex i is τ ( i ) = ( d i 2 ) displaystyle tau (i)= binom d_ i 2 , assuming d i ≥ 2 displaystyle d_ i geq 2 . Thus we can express τ ( G ) = 1 3 ∑ i ∈ V τ ( i ) displaystyle tau (G)= frac 1 3 sum _ iin V tau (i) . Now, for a vertex i displaystyle i with d i ≥ 2 displaystyle d_ i geq 2 , the clustering coefficient c ( i ) displaystyle c(i) of vertex i displaystyle i is the fraction of triples for vertex i displaystyle i that are closed, and can be measured as δ ( i ) τ ( i ) displaystyle frac delta (i) tau (i) . Thus, the clustering coefficient C ( G ) displaystyle C(G) of graph G displaystyle G is given by C ( G ) = 1 N 2 ∑ i ∈ V , d i ≥ 2 c ( i ) displaystyle C(G)= frac 1 N_ 2 sum _ iin V,d_ i geq 2 c(i) , where N 2 displaystyle N_ 2 is the number of nodes with degree at least 2. Transitivity[edit] Another measure for the presence of triadic closure is transitivity, defined as T ( G ) = 3 δ ( G ) τ ( G ) displaystyle T(G)= frac 3delta (G) tau (G) .
Causes and effects[edit]
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.
^ Georg Simmel, originator of the concept: "Facebook" article at the New York Times website. Retrieved on December 21, 2007. ^ Working concept 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. ^ a b c d Easley, D, & Kleinberg, J. (2010). Networks, crowds, and markets: reasoning about a highly connected world. Cornell, NY: Cambridge Univ Pr. ^ 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. v t e Social networks and social media Types City Personal Professional Sexual Value Networks
Services List of social networking websites List of virtual communities with more than 1 million users List of virtual communities with more than 100 million active users Concepts and theories Assortative mixing
Interpersonal bridge
Organizational network analysis
Small-world experiment
Social aspects of television
Social capital
Social data revolution
Social exchange theory
Social identity theory
Models and processes Aggregation
Change detection
Collaboration graph
Collaborative consumption
Giant Global Graph
Lateral communication
Social graph
Economics Collaborative finance Social commerce Phenomena Community recognition
Complex contagion
Consequential strangers
Friend of a friend
Friendship paradox
Six degrees of separation
Social invisibility
Related topics Researchers User profile Viral messages Virtu |