Section 7.8: Groups of vertices - Naval Postgraduate School

Section 7.8: Groups of vertices - Naval Postgraduate School

Section 8.6: Clustering Coefficients By: Ralucca Gera, NPS Most pictures are from Newmans textbook Clustering coefficients for real networks The clustering coefficients measure the average probability that two neighbors of a vertex are themselves neighbors (a measure of the density of triangles in a network). There are three versions:

1. Clustering coeff. of G: 2. Local Clustering coefficient: 3. Avg. clustering coeff. of G: An example 3 Clustering coeff distrrribution example in Gephi h =

1 5 2 () One triangle paths, only 5 displayed Statistics for real networks = clustering coefficient

= ave clustering coefficient 5 Observed vs. expected values for Network Observed Expected value based on random graphs

Collaboration of physicists C = .45 C= .0023 Food webs C = . 16 (or .12) similar Internet

C = .012 ws ws C = .84 6 Source: N. Przulj. Graph theory analysis of protein-protein interactions. 2005. Explanations?

The exact reason for this phenomenon is not well understood, but it may be connected with The structure of the graph (since the random one lacks it) The formation of groups or communities E.g., in social networks triadic closure 7 as a function of the network size Source: R. Albert and A. L. Barabasi. Statistical mechanics of

complex networks. Reviews of Modern Physics, 74:4797, 2002 8 as a function of degree PPI: protein-protein interaction netw. SF = scale free synthetic network Source: N. Przulj, D. G. Corneil, and I. Jurisica. Modeling interactome: Scale free or geometric? arXiv:qbio.

MN/0404017, 2004. 9 Section 8.6.1:Local clustering coefficient If we calculate the local clustering coefficient of each vertex in a network an interesting pattern occurs On average, vertices of higher degree exhibit lower local clustering Internet network.

For nodes of degree : , where 1 Thoughts on why this occurs? 10 Section 8.6.1:Local clustering coefficient Possible explanations for the decrease in as degree increases: Vertices tend to group in communities, sharing

mostly neighbors within the same community Thus some vertices have small/large degree based on the size of the community Smaller communities are denser larger Communities are generally connected by large degree nodes, and being a connector will decrease its value of of these large degree 11 nodes. Extensions Clustering coefficient measures the density of

in networks The density of other small groups of vertices can be studied as well (density of motifs) 12 Graphlet frequency in Scale Free netw Source: N. Przulj, D. G. Corneil, and I. Jurisica. Modeling interactome: Scale free or geometric? arXiv:qbio. MN/0404017, 2004. 13

Recently Viewed Presentations

  • Astronomy A BEGINNERS GUIDE TO THE UNIVERSE EIGHTH

    Astronomy A BEGINNERS GUIDE TO THE UNIVERSE EIGHTH

    The condensation sequence theory explains why. our planet Earth has water and rain. stars are more likely to form large planets orbiting very near. terrestrial planets are different from jovian planets. the Moon formed near Earth. Pluto has such a...
  • TrackSat-1 Manual R pido - PowerPoint PPT Presentation

    TrackSat-1 Manual R pido - PowerPoint PPT Presentation

    TrackSat-1 Manual R pido PowerPoint Presentation. Download Presentation. TrackSat-1 Manual R pido. Loading in 2 Seconds...
  • مهارات القرن الحادي ... - schoolnet.edu.lb

    مهارات القرن الحادي ... - schoolnet.edu.lb

    كيف يمكن للتكنولوجيا أن تدعم التعلم القائم على . المش. ا
  • Check-in/Check-out - BET-C

    Check-in/Check-out - BET-C

    Learning Objectives Describe the CICO program What are the 8 steps in the CICO List the 4 elements for implementing CICO Fishin' for More Info? [email protected] www.koi-education.com 480.420.6564 Students who are not successful with Tier 1 interventions alone, need additional...
  • Diapositiva 1 - UNAM

    Diapositiva 1 - UNAM

    La vista humana y la percepción de su entorno. Uno de los sentidos que más se utiliza en la Arquitectura, la Pintura y las Artes Plásticas es el sentido de la vista, por lo que el comportamiento del ojo humano...
  • Jean Baptiste "Joseph Fourier"

    Jean Baptiste "Joseph Fourier"

    Musical instruments produce sound as a result of the vibration of a physical object such as a string on a violin, guitar, or piano, or a column of air in a brass or woodwind instrument. This vibration causes a periodic...
  • Electronic Triage comes to the North Bay Regional

    Electronic Triage comes to the North Bay Regional

    I was invited to a meeting by my manager that had something to do with the ED wanting to document something. I walked into the room totally unprepared for what was about to transpire. At the helm of the ship...
  • THE NEW CALIPHATE (ISIS-IS) Radical Islam at War

    THE NEW CALIPHATE (ISIS-IS) Radical Islam at War

    John Jandali. National Security Forum. 7 August 2014. 7 Aug 2014. NSF Caliphate. 7 Aug 2014. NSF Caliphate. Middle East. 7 Aug 2014. NSF Caliphate. The New Caliphate. 7 Aug 2014. NSF Caliphate. The World as ISIS Sees It. From...