Introduction to the formal analysis of social networks - Version 2
Luis R .  Izquierdo

Revision control

Version 2 corrects a bug in the functions Betweenness[v_Integer,g_Graph] and Betweenness[g_Graph]. We are grateful to Francesc Comellas for letting us know that the mentioned functions were not working properly in version 1.

Packages

\(\(\(\(Needs["DiscreteMath`Combinatorica`"];\)\  (*\ 
      For\ the\ analysis\ of\ \(\(graphs\)\(.\)\)\ *) 

    \(Needs["Graphics`Graphics`"];\)\  (*\ 
      For\ the\ \(\(Histograms\)\(.\)\)\ *) 

    \(Needs["Statistics`DataManipulation`"];\)\)\(\ \)\( (*\ 
      For\ Frequencies, \ 
      used\ in\ the\ function\ \(\(ReachabilityCloseness\)\(.\)\)\ *) \)\)\)

Functions

Off[General::spell]; 

  
ReciprocatedEdges[g_Graph] := 
        Module[{adjMatrix = ToAdjacencyMatrix[g]}, 
          Count[adjMatrix + Transpose[adjMatrix], 
            2, {2}]];

  

MaximumNClique[g_Graph, n_Integer] := 
        MaximumClique[
          RemoveSelfLoops[
            RemoveMultipleEdges[
              GraphPower[g, 
                n]]]];


 (* Returns true if c is an n - clique,  
      i . e .  
          allowing for paths of any length no greater than n .  
          False otherwise. *) 

NCliqueQ[g_Graph, n_Integer, c_List] := 
        CliqueQ[RemoveSelfLoops[RemoveMultipleEdges[GraphPower[g, n]]], 
          c];

  

MaximumNClans[g_Graph, n_Integer] := 
        Module[{listOfDegrees, allSuitableNodes = Range[V[g]], 
            clans = {}}, 

 (* 
            A clan is,  in particular,  a clique,  
            so find out the maximum possible size of the clan. *) 
maxSizeOfClan = 
            Length[MaximumNClique[g, 
                n]]; 

 (* 
            There is no need to consider the nodes of degree maxSizeOfClan - 
              2 or less (in the powered graph) as they cannot be part of an n - 
              clique or an n - clan. *) 
listOfDegrees = 
            Degrees[RemoveSelfLoops[
                RemoveMultipleEdges[
                  GraphPower[g, n]]]]; 
allSuitableNodes = 
            Select[allSuitableNodes,  (listOfDegrees[[#]] ≥  maxSizeOfClan - 
                      1) &]; 

While[
            Length[clans] == 0  &&  
              maxSizeOfClan ≥  
                1, 
possibleClans = 
              Subsets[allSuitableNodes, {maxSizeOfClan}]; 
clans = 
              Select[possibleClans, 
                CompleteQ[
                    RemoveSelfLoops[
                      RemoveMultipleEdges[
                        GraphPower[InduceSubgraph[g, #], 
                          n]]]] &]; 
maxSizeOfClan--;
]; 

clans
];


 (* Returns true if c is an n - clan,  
      i . e .  
          allowing for paths of any length no greater than n .  
          False otherwise. *) 

NClanQ[g_Graph, n_Integer, c_List] := 
        CompleteQ[
          RemoveSelfLoops[
            RemoveMultipleEdges[
              GraphPower[InduceSubgraph[g, c], 
                n]]]];

  

\(\(Clustering[v_Integer, g_Graph] := 
        Module[
{nbrs, 
            subGraph}, 

nbrs = 
            Complement[Neighborhood[g, v, 1], {v}]; 
If[
            Length[nbrs] < 2, 
            Return["Undefined"]]; 

subGraph = 
            InduceSubgraph[g, nbrs]; 

If[
            UndirectedQ[g], 
Return[
              2*M[subGraph]/\((V[
                        subGraph]*\((V[subGraph] - 
                          1)\))\)], 
Return[
              M[subGraph]/\((V[
                      subGraph]*\((V[subGraph] - 
                        1)\))\)]
];
];\)

 (*\ 
      An\ n - clan\ is\ an\ n - 
        clique\ where\ all\ ties\ among\ members\ of\ the\ n - 
        clique\ occur\ through\ members\ of\ the\ n - 
        clique . \ This\ function\ returns\ a\ list\ of\ all\ the\ n - 
        clans\ of\ maximum\ size, \ 
      i . e . \ 
          allowing\ for\ paths\ of\ any\ length\ no\ greater\ than\ \(\(n\)\(.\)\)\ *) 
\)
MaximumNClans[g_Graph, n_Integer] := 
        Module[{listOfDegrees, allSuitableNodes = Range[V[g]], 
            clans = {}}, 

 (* 
            A clan is,  in particular,  a clique,  
            so find out the maximum possible size of the clan. *) 
maxSizeOfClan = 
            Length[MaximumNClique[g, 
                n]]; 

 (* 
            There is no need to consider the nodes of degree maxSizeOfClan - 
              2 or less (in the powered graph) as they cannot be part of an n - 
              clique or an n - clan. *) 
listOfDegrees = 
            Degrees[RemoveSelfLoops[
                RemoveMultipleEdges[
                  GraphPower[g, n]]]]; 
allSuitableNodes = 
            Select[allSuitableNodes,  (listOfDegrees[[#]] ≥  maxSizeOfClan - 
                      1) &]; 

While[
            Length[clans] == 0  &&  
              maxSizeOfClan ≥  
                1, 
possibleClans = 
              Subsets[allSuitableNodes, {maxSizeOfClan}]; 
clans = 
              Select[possibleClans, 
                CompleteQ[
                    RemoveSelfLoops[
                      RemoveMultipleEdges[
                        GraphPower[InduceSubgraph[g, #], 
                          n]]]] &]; 
maxSizeOfClan--;
]; 

clans
];

 (* 
      Returns true if c is an n - clan,  
      i . e .  
          allowing for paths of any length no greater than n .  
          False otherwise. *) 

NClanQ[g_Graph, n_Integer, c_List] := 
        CompleteQ[
          RemoveSelfLoops[
            RemoveMultipleEdges[
              GraphPower[InduceSubgraph[g, c], 
                n]]]];


 (* 
      The clustering coefficient of a node is the ratio of existing links connecting the node' s neighbours to each other, 
      to the maximum possible number of such links .  
          For nodes with fewer than two neighbours the clustering coefficient is undefined.*) 

\(\(Clustering[v_Integer, g_Graph] := 
        Module[
{nbrs, 
            subGraph}, 

nbrs = 
            Complement[Neighborhood[g, v, 1], {v}]; 
If[
            Length[nbrs] < 2, 
            Return["Undefined"]]; 

subGraph = 
            InduceSubgraph[g, nbrs]; 

If[
            UndirectedQ[g], 
Return[
              2*M[subGraph]/\((V[
                        subGraph]*\((V[subGraph] - 
                          1)\))\)], 
Return[
              M[subGraph]/\((V[
                      subGraph]*\((V[subGraph] - 
                        1)\))\)]
];
];\)

 (*\ 
      This\ function\ returns\ a\ list\ of\ 2 - 
        dimensional\ vectors . \ 
            The\ first\ component\ of\ each\ vector\ is\ a\ number\ nbrs\ denoting\ a\ number\ of\ neighbours . \ 
            The\ second\ component\ is\ the\ average\ number\ of\ edges\ between\ the\ neighbours\ of\ every\ node\ that\ has\ nbrs\ neighbours . \ 
            It\ works\ for\ both\ directed\ and\ undirected\ \(\(graphs\)\(.\)\)\ *) 
\)
\(\(Clustering[g_Graph] := 
        Module[
{listOfNeighbourhoods, 
            listOfNeighbourhoodsGreaterThan1, listOfSubgraphs, 
            myClusteringList, nOfNbrs, listOfDiffOutDegress, 
            totalNumEdges}, 

listOfNeighbourhoods = 
            Map[Complement[Neighborhood[g, #, 1], {#}] &, 
              Range[V[g]]]; 
listOfNeighbourhoodsGreaterThan1 = 
            Select[listOfNeighbourhoods, \((Length[#] > 
                    1)\) &]; 
listOfSubgraphs = 
            Map[InduceSubgraph[g, #] &, 
              listOfNeighbourhoodsGreaterThan1]; 

 (*\ 
            myClusteringList\ is\ a\ list\ of\ two\ elements\ for\ each\ node\ with\ 2\ or\ more\ neighbours . \ 
                The\ first\ element\ of\ the\ list\ is\ the\ number\ of\ neighbours, \ 
            and\ the\ second\ element\ is\ the\ number\ of\ edges\ between\ the\ neighbours . \ 
                It\ works\ for\ both\ directed\ and\ undirected\ \(\(graphs\)\(.\)\)\ *) 
myClusteringList = 
            Map[{V[#], M[#]} &, 
              listOfSubgraphs]; 

nOfNbrs = Length[listOfNeighbourhoodsGreaterThan1]; 
listOfDiffOutDegress = 
            Union[myClusteringList[\([All, 
                  1]\)]]; 
totalNumEdges = 
            Table[0, {Length[
                  listOfDiffOutDegress]}]; 

For[i = 1, 
            i ≤ 
              nOfNbrs, \(i++\), 
\(totalNumEdges[\([\(Position[listOfDiffOutDegress, 
                        myClusteringList[\([i, 1]\)], 1, 1]\)[\([1, 
                        1]\)]]\)] += 
                myClusteringList[\([i, 
                    2]\)];\)
]; 

If[
            UndirectedQ[g], 
Inner[List, 
              listOfDiffOutDegress, \ 
              2*totalNumEdges/\((listOfDiffOutDegress*\((listOfDiffOutDegress - 1)\)*Map[Count[myClusteringList[\([All, 1]\)], #] &, 
                        listOfDiffOutDegress])\), 
              List], 
Inner[List, listOfDiffOutDegress, \ 
              totalNumEdges/\((listOfDiffOutDegress*\((listOfDiffOutDegress - 
                        1)\)*Map[Count[myClusteringList[\([All, 1]\)], #] &, 
                      listOfDiffOutDegress])\), 
              List], 
]
];\)

 (*\ 
      The\ closeness\ centrality\ of\ a\ node\ using\ geodesic\ distance\ is\ the\ reciprocal\ of\ the\ sum\ of\ geodesic\ distances\ from\ the\ node\ to\ all\ other\ vertices\ in\ the\ graph . \ 
          This\ function\ returns\ the\ closeness\ centrality\ using\ geodesic\ distance\ of\ every\ node\ in\ the\ \(\(graph\)\(.\)\)\ *) 
\)
\(\(GeodesicCloseness[g_Graph] := 
        1/Total[AllPairsShortestPath[
              g]];\)


 (*\ This\ function\ returns\ a\ list\ with\ the\ reachability\ closeness\ of\ each\ node\ in\ the\ graph . \ 
          The\ reachability\ closeness\ of\ a\ node\ is\ calculated\ by\ summing\ up\ the\ proportion\ of\ other\ nodes\ reached\ \((for\ the\ first\ time)\)\ at\ a\ given\ distance, 
      appropriately\ weighted . \ In\ this\ case\ the\ weights\ used\ are\ 1/
          n\ where\ n\ denotes\ the\ distance\ between\ the\ nodes \((e  
              g . \ 1\ for\ nodes\ at\ distance\ 1, \ ½\ for\ nodes\ at\ distance\ 2  …)\)\ *) 
\)
ReachabilityCloseness[g_Graph] := 
        Module[{freqLists}, 
freqLists = 
            Map[Rest[Frequencies[#]] &, 
              AllPairsShortestPath[
                g]]; 
Map[(Total[#[[All, 
                          1]]*(1/#[[All, 2]])]) &, 
              freqLists]/(V[g] - 
                1)
];

 (* 
      This function returns a matrix indicating the number of shortest paths between any two nodes in the network.*) 

Options[
          NumberOfShortestPaths] = {CheckGraphIsConnected -> 
            True};
\(\(NumberOfShortestPaths[g_Graph, opts___?OptionQ] := 
        Module[
{distancesMatrix\ , adjMatrix\ , 
            powersOfAdjMatrix\ }, 

checkForConnected = 
            CheckGraphIsConnected /. 
              Flatten[{opts, 
                  Options[NumberOfShortestPaths]}]; 
 (*\ 
            Replace\ \(( /. )\)\ returns\ the\ result\ from\ using\ the\ first\ rule\ that\ \(\(applies\)\(.\)\)\ *) 
If[
            checkForConnected, 
\(If[\((UndirectedQ[
                        g]\  && \ \(! ConnectedQ[
                          g]\))\)\  || \ \((\(! UndirectedQ[
                          g]\)\  && \ \(! ConnectedQ[g, 
                          Strong]\))\), \ 
Print["The graph is not (strongly) connected"]; \ 
                Return[];
];\)
]; 

distancesMatrix\  = \ 
            AllPairsShortestPath[g]; 
If[
            Not[checkForConnected], 
            distancesMatrix = 
              Replace[distancesMatrix, ∞ -> 
                  0, {2}]]; 
 (*\ 
            A\ distance\ of\ 0\ will\ give\ 0\ shortest\ paths\ between\ those\ \(\(nodes\)\(.\)\)\ *) 

adjMatrix\  = \ ToAdjacencyMatrix[g]; 
powersOfAdjMatrix\  = \ 
            NestList[\((# . adjMatrix)\) &, adjMatrix, 
              Max[distancesMatrix] - 
                1]; 

PrependTo[
            powersOfAdjMatrix, 
            Table[0, {V[g]}, {V[g]}]]; 
 (*\ 
            We\ prepend\ the\ matrix\ that\ pairs\ showing\ a\ distance\ of\ 0\ will\ read . \ These\ pairs\ are\ those\ that\ are\ not\ connected, \ 
            and\ the\ pairs\ consisting\ of\ a\ node\ with\ \(\(itself\)\(.\)\)\ *) 
MapIndexed[\((powersOfAdjMatrix[\([#1, 
                    Apply[Sequence, #2]]\)])\) &, 
            distancesMatrix + 
              Table[1, {V[g]}, {V[
                    g]}], {2}]
];\)


 (*\ 
      This\ function\ returns\ the\ betweeness\ of\ node\ v . \ 
          The\ betweenness\ of\ a\ node\ v\ is\ calculated\ by\ computing, \ 
      for\ every\ pair\ of\ other\ nodes\ s, 
      t\ in\ the\ network\ \((s ≠ v ≠ t)\), \ 
      the\ fraction\ of\ all\ the\ shortest\ paths\ between\ s\ and\ t\ that\ pass\ through\ v . \ 
          These\ \((n\ –\ 1)\) \((n\ –\ 2)\)\ fractions\ are\ then\ summed\ up . \ 
          The\ idea\ in\ this\ algorithm\ is\ that\ the\ number\ of\ shortest\ paths\ between\ s\ and\ s\ that\ do\ not\ pass\ through\ a\ node\ v\ are\ the\ number\ of\ paths\ between\ s\ and\ t\ OF\ LENGTH\ EQUAL\ TO\ THE\ DISTANCE\ BETWEEN\ s\ AND\ t\ IN\ THE\ ORIGINAL\ GRAPH, \ 
      in\ a\ graph\ where\ node\ v\ has\ been\ \(\(deleted\)\(.\)\)\ *) 
\)
\(\(Betweenness[v_Integer, g_Graph] := 
        Module[{distancesMatrix, adjMatrix, powersOfAdjMatrix, 
            nShortestPaths, adjMatrixWithoutVertex, 
            powersOfAdjMatrixWithoutVertex, 
            nShortestPathsNotThroughV}, 

If[\((UndirectedQ[
                    g]\  && \ \(! ConnectedQ[
                      g]\))\)\  || \ \((\(! UndirectedQ[
                      g]\)\  && \ \(! ConnectedQ[g, 
                      Strong]\))\), \ 
Print["The graph is not (strongly) connected"]; \ 
            Return[];
]; 

distancesMatrix\  = \ 
            AllPairsShortestPath[
              g]; 

 (*\ 
            Calculate\ the\ number\ of\ shortest\ paths\ between\ any\ two\ nodes\ in\ the\ graph\ *) 
adjMatrix\  = \ 
            ToAdjacencyMatrix[g]; 
powersOfAdjMatrix\  = \ 
            NestList[\((# . adjMatrix)\) &, adjMatrix, 
              Max[distancesMatrix] - 1]; 
PrependTo[
            powersOfAdjMatrix, Table[0, {V[g]}, {V[g]}]];  (*\ 
            We\ prepend\ the\ matrix\ that\ pairs\ showing\ a\ distance\ of\ 0\ will\ read . \ These\ pairs\ are\ those\ that\ are\ not\ connected, \ 
            
            and\ the\ pairs\ consisting\ of\ a\ node\ with\ \(\(itself\)\(.\)\)\ *) 
nShortestPaths = 
            MapIndexed[\((powersOfAdjMatrix[\([#1, 
                      Apply[Sequence, #2]]\)])\) &, 
              distancesMatrix + 
                Table[1, {V[g]}, {V[
                      g]}], {2}]; 

 (*\ 
            Calculate\ the\ number\ of\ paths\ between\ i\ and\ j\ OF\ LENGTH\ EQUAL\ TO\ THE\ DISTANCE\ BETWEEN\ i\ AND\ j\ IN\ THE\ ORIGINAL\ GRAPH, \ 
            in\ a\ graph\ where\ node\ v\ has\ been\ deleted . \ 
                This\ is\ the\ number\ of\ shortest\ paths\ between\ i\ and\ j\ that\ do\ not\ pass\ through\ node\ v\ in\ the\ original\ \(\(graph\)\(.\)\)\ *) 
adjMatrixWithoutVertex\  = \ 
            Drop[adjMatrix, {v}, {v}]; 
powersOfAdjMatrixWithoutVertex\  = \ 
            NestList[\((# . adjMatrixWithoutVertex)\) &, 
              adjMatrixWithoutVertex, 
              Max[distancesMatrix] - 1]; 
PrependTo[
            powersOfAdjMatrixWithoutVertex, Table[0, {V[g]}, {V[g]}]];  (*\ 
            We\ prepend\ the\ matrix\ that\ pairs\ showing\ a\ distance\ of\ 0\ will\ read . \ These\ pairs\ are\ those\ that\ are\ not\ connected, \ 
            and\ the\ pairs\ consisting\ of\ a\ node\ with\ \(\(itself\)\(.\)\)\ *) 
nShortestPathsNotThroughV = 
            MapIndexed[\((powersOfAdjMatrixWithoutVertex[\([#1, 
                      Apply[Sequence, #2]]\)])\) &, 
              Drop[distancesMatrix, {v}, {v}] + 
                Table[1, {V[g] - 1}, {V[g] - 
                      1}], {2}]; 

 (*\ 
            Return\ the\ betweenness\ *) 
Total[\((Drop[
                    nShortestPaths, {v}, {v}] - 
                  nShortestPathsNotThroughV)\)/\((Drop[
                    nShortestPaths, {v}, {v}] - IdentityMatrix[V[g] - 1])\), 
            2]
];\)


 (*\ 
      This\ function\ returns\ a\ list\ with\ the\ betweeness\ of\ every\ node\ in\ the\ network . \ 
          The\ betweenness\ of\ a\ node\ v\ is\ calculated\ by\ computing, \ 
      for\ every\ pair\ of\ other\ nodes\ s, 
      t\ in\ the\ network\ \((s ≠ v ≠ t)\), \ 
      the\ fraction\ of\ all\ the\ shortest\ paths\ between\ s\ and\ t\ that\ pass\ through\ v . \ 
          These\ \((n\ –\ 1)\) \((n\ –\ 2)\)\ fractions\ are\ then\ summed\ up . \ 
          The\ idea\ in\ this\ algorithm\ is\ that\ the\ number\ of\ shortest\ paths\ between\ s\ and\ s\ that\ do\ not\ pass\ through\ a\ node\ v\ are\ the\ number\ of\ paths\ between\ s\ and\ t\ OF\ LENGTH\ EQUAL\ TO\ THE\ DISTANCE\ BETWEEN\ s\ AND\ t\ IN\ THE\ ORIGINAL\ GRAPH, \ 
      in\ a\ graph\ where\ node\ v\ has\ been\ \(\(deleted\)\(.\)\)\ *) 
\)
\(\(Betweenness[g_Graph] := 
        Module[{nNodes, distancesMatrix, adjMatrix, powersOfAdjMatrix, 
            nShortestPaths, v, adjMatrixWithoutVertex, 
            powersOfAdjMatrixWithoutVertex, nShortestPathsNotThroughV, 
            betweennessList}, 

If[\((UndirectedQ[
                    g]\  && \ \(! ConnectedQ[
                      g]\))\)\  || \ \((\(! UndirectedQ[
                      g]\)\  && \ \(! ConnectedQ[g, 
                      Strong]\))\), \ 
Print["The graph is not (strongly) connected"]; \ 
            Return[];
]; 

distancesMatrix\  = \ 
            AllPairsShortestPath[g]; 
nNodes = 
            V[g]; 

 (*\ 
            Calculate\ the\ number\ of\ shortest\ paths\ between\ any\ two\ nodes\ in\ the\ graph\ *) 
adjMatrix\  = \ 
            ToAdjacencyMatrix[g]; 
powersOfAdjMatrix\  = \ 
            NestList[\((# . adjMatrix)\) &, adjMatrix, 
              Max[distancesMatrix] - 1]; 
PrependTo[
            powersOfAdjMatrix, Table[0, {nNodes}, {nNodes}]];  (*\ 
            We\ prepend\ the\ matrix\ that\ pairs\ showing\ a\ distance\ of\ 0\ will\ read . \ These\ pairs\ are\ those\ that\ are\ not\ connected, \ 
            and\ the\ pairs\ consisting\ of\ a\ node\ with\ \(\(itself\)\(.\)\)\ *) 
nShortestPaths = 
            MapIndexed[\((powersOfAdjMatrix[\([#1, 
                      Apply[Sequence, #2]]\)])\) &, 
              distancesMatrix + 
                Table[1, {nNodes}, {nNodes}], {2}]; 

betweennessList = {}; 
 (*\ 
            Calculate\ the\ number\ of\ paths\ between\ i\ and\ j\ OF\ LENGTH\ EQUAL\ TO\ THE\ DISTANCE\ BETWEEN\ i\ AND\ j\ IN\ THE\ ORIGINAL\ GRAPH, \ 
            in\ a\ graph\ where\ node\ v\ has\ been\ deleted . \ 
                This\ is\ the\ number\ of\ shortest\ paths\ between\ i\ and\ j\ that\ do\ not\ pass\ through\ node\ v\ in\ the\ original\ \(\(graph\)\(.\)\)\ *) 
For[v = 1, 
            v ≤ 
              nNodes, \(v++\), 
adjMatrixWithoutVertex\  = \ Drop[adjMatrix, {v}, {v}]; 
            powersOfAdjMatrixWithoutVertex\  = \ 
              NestList[\((# . adjMatrixWithoutVertex)\) &, 
                adjMatrixWithoutVertex, 
                Max[distancesMatrix] - 1]; 
PrependTo[
              powersOfAdjMatrixWithoutVertex, 
              Table[0, {nNodes}, {nNodes}]];  (*\ 
              We\ prepend\ the\ matrix\ that\ pairs\ showing\ a\ distance\ of\ 0\ will\ read . \ These\ pairs\ are\ those\ that\ are\ not\ connected, \ 
              and\ the\ pairs\ consisting\ of\ a\ node\ with\ \(\(itself\)\(.\)\)\ *) 
nShortestPathsNotThroughV = 
              MapIndexed[\((powersOfAdjMatrixWithoutVertex[\([#1, 
                        Apply[Sequence, #2]]\)])\) &, 
                Drop[distancesMatrix, {v}, {v}] + 
                  Table[1, {nNodes - 1}, {nNodes - 
                        1}], {2}]; 

AppendTo[betweennessList, 
              Total[\((Drop[nShortestPaths, {v}, {v}] - 
                      nShortestPathsNotThroughV)\)/\((Drop[
                        nShortestPaths, {v}, {v}] - 
                      IdentityMatrix[V[g] - 1])\), 
                2]];
]; 

 (*\ 
            Return\ the\ betweenness\ *) 
betweennessList
];\)\)

Basics Concepts and Terminology

myBinaryTree = CompleteBinaryTree[50];

    
g1 = 
        ShowGraph[myBinaryTree,  
          DisplayFunction -> Identity];
g2 = 
        ShowGraph[SpringEmbedding[myBinaryTree, 200, 0.05],  
          DisplayFunction -> Identity];
g3 = 
        ShowGraph[RadialEmbedding[myBinaryTree],  
          DisplayFunction -> Identity];
g4 = 
        ShowGraph[CircularEmbedding[myBinaryTree],  
          DisplayFunction -> Identity];

    
Show[GraphicsArray[{{g1, g2}, {g3, g4}}]];

Representing Social Network Data

\(\(\(SeedRandom[2];\)\(
\)
    \)\)
myGraph = RandomGraph[5, 0.3, Type -> Directed];
ShowGraph[myGraph,  VertexNumber -> True, 
        TextStyle -> {FontSize -> 16}, 
        VertexNumberPosition -> {-0.01, -0.02}];

myAdjMatrix = ToAdjacencyMatrix[myGraph];
Table[MatrixForm[MatrixPower[myAdjMatrix, i]], {i, 5}]

Basic Properties of Networks and Actors

SeedRandom[2];

    
myGraph = RandomGraph[5, 0.3, Type -> Directed];
ShowGraph[myGraph,  VertexNumber -> True, 
        TextStyle -> {FontSize -> 16}, 
        VertexNumberPosition -> {-0.01, -0.02}];

Print["Number of nodes: ", V[myGraph]];
Print["Number of edges: ",  M[myGraph]];

If[UndirectedQ[myGraph], 
        Print["Density: ", 
          2 M[myGraph]/(V[myGraph] (V[myGraph] - 1))], 
        Print["Density: ", 
          M[myGraph]/(V[myGraph] (V[myGraph] - 1))]];

Print["The in-degree of each node in the network is: ", 
        InDegree[myGraph]];
Print["The out-degree of each node in the network is: ", 
        OutDegree[myGraph]];

DegreeSequence[MakeUndirected[myGraph]]

myList = DegreeSequence[CompleteBinaryTree[40]]

ShowGraph[
        SpringEmbedding[RealizeDegreeSequence[myList], 100, 
          0.05]];

Social Distance and Related Concepts

\(\(\(SeedRandom[2];\)\(
\)
    \)\)
myGraph = RandomGraph[5, 0.3, Type -> Directed];
\(\(\(ShowGraph[myGraph, \ VertexNumber -> True, 
        TextStyle -> {FontSize -> 16}, 
        VertexNumberPosition -> {\(-0.01\), \(-0.02\)}];\)\(
\)
    \)\)
Print["All pairs distances: ", 
        MatrixForm[AllPairsShortestPath[myGraph]]];

myAdjMatrix = {{0, 1, 0, 0, 0}, {1, 0, 1, 1, 1}, {0, 1, 0, 1, 0}, {0, 
            1, 1, 0, 1}, {0, 1, 0, 1, 0}};
graphFig6 = 
        SetVertexLabels[
          FromAdjacencyMatrix[myAdjMatrix], {A, B, C, 
            D, "E"}];
ShowGraph[graphFig6, 
        TextStyle ->  {FontSize ->  16}];

Table[
        Print["Number of walks of length ", i, " between nodes: ",  
          MatrixForm[MatrixPower[myAdjMatrix, i]]], {i, 4}];

?ExtractCycles
ShowGraph[
        Highlight[
          graphFig6, {Partition[ExtractCycles[graphFig6][[1]], 2, 
              1]}]];

Print["Shortest path between A (node 1) and C (node 3): ", 
        ShortestPath[graphFig6, 1, 3]];
ShowGraph[
        Highlight[
          graphFig6, {Partition[ShortestPath[graphFig6, 1, 3], 2, 
              1]}]];

Print["The eccentricity of each node in the network is: ", 
        Eccentricity[graphFig6]];
Print["The diameter of the network is: ", 
        Diameter[graphFig6]];
Print["The radius of the network is: ", 
        Radius[graphFig6]];
Print["The peripheral vertices are: ",  
        Position[Eccentricity[graphFig6], Diameter[graphFig6]]];
Print["The nodes in the centre of the network are: ",  
        GraphCenter[graphFig6]];

Connection and Connectivity

Print["Is the graph in fig. 6 connected? ",  
        ConnectedQ[graphFig6]];

Print["Is my graph strongly connected? ",  
        ConnectedQ[myGraph, Strong]];
Print["The strongly connected components in my graph are: ",  
        StronglyConnectedComponents[myGraph]];

Print["Is my graph weakly connected? ",  
        ConnectedQ[myGraph, Weak]];
Print["The weakly connected components in my graph are: ",  
        WeaklyConnectedComponents[myGraph]];

?VertexConnectivity
Print["The vertex-connectivity of graph in fig. 6 is: ",  
        VertexConnectivity[graphFig6]];

?ArticulationVertices
Print["The articulation vertices of graph in fig. 6 are: ",  
        ArticulationVertices[graphFig6]];

?EdgeConnectivity
Print["The edge-connectivity of graph in fig. 6 is: ",  
        EdgeConnectivity[graphFig6]];

?Bridges
Print["The bridges of graph in fig. 6 are: ",  
        Bridges[graphFig6]];

ShowGraph[
        myFragmentedGrid = 
          InduceSubgraph[GridGraph[50, 50], RandomSubset[2500]], 
        VertexStyle -> Disk[0]];
c = Map[Length, ConnectedComponents[myFragmentedGrid]];
Histogram[c, HistogramCategories -> Range[0, Max[c] + 1], 
        PlotLabel -> "Distribution of the size of \
components"];

Local Structures in Networks

graphFig8 = EmptyGraph[3, Type -> Directed];
graphFig8 = 
        AddEdges[graphFig8, {{1, 2}, {2, 3}, {2, 1}}];
ShowGraph[graphFig8, 
        VertexNumber -> True];

    
Print["Reciprocated relations relative to all possible relations: \
",  ReciprocatedEdges[
            graphFig8]/(V[
                graphFig8]*(V[graphFig8] - 1))];
\(\(Print["Reciprocated relations relative to existing relations: ", \ ReciprocatedEdges[graphFig8]/M[graphFig8]];\)\)

?TransitiveQ
?TransitiveClosure
?TransitiveReduction

SeedRandom[0]
myRandomGraph = RandomGraph[10, 0.7];
ShowGraph[
        Highlight[
          myRandomGraph, {MaximumClique[myRandomGraph]}]];

Print["Any subset of the vertices of a complete graph forms a \
clique: ",  CliqueQ[CompleteGraph[10], RandomSubset[10]]];

ShowGraph[
        Highlight[
          myRandomGraph, {MaximumNClique[myRandomGraph, 2]}]];

ShowGraph[Highlight[Cycle[6], {1, 3, 5}], 
        VertexNumber -> True];
Print["Do nodes 1, 3, and 5 form a 2-Clique? ", 
        NCliqueQ[Cycle[6], 2, {1, 3, 5}]];
Print["Do nodes 1, 2, 3, and 5 form a 2-Clique?", 
        NCliqueQ[Cycle[6], 2, {1, 2, 3, 5}]];

Print["Do nodes 1, 3, and 5 form a 2-Clan? ", 
        NClanQ[Cycle[6], 2, {1, 3, 5}]];
Print["2-Clans of maximum size in a cycle with 6 nodes: ", 
        MaximumNClans[Cycle[6], 2]];

Print["The clustering coeff. of the blue node in the second graph \
of fig. 9 is: ",  
        Clustering[1, DeleteEdge[CompleteGraph[4], {2, 4}]]];

myListOfClusteringCoefficients = 
        Clustering[RandomGraph[100, 0.6]];
minDegree = 
        Min[myListOfClusteringCoefficients[[All, 1]]];
ListPlot[myListOfClusteringCoefficients, 
        AxesOrigin -> {minDegree, 0}, 
        PlotRange -> {{minDegree, Automatic}, {0, 1}}, 
        FrameLabel -> {"# of Neighbours", "Avg. Clustering \
Coefficient"}, Frame -> True, 
        PlotStyle -> PointSize[0.02]];

Print["The clustering coefficient list of my fragmented grid is: \
",  Clustering[myFragmentedGrid]];

Centrality and Power

graphFig10 = 
        AddEdges[
          EmptyGraph[
            5], {{1, 2}, {1, 3}, {1, 4}, {1, 5}, {3, 4}, {4, 
              5}}];
ShowGraph[graphFig10, VertexNumber -> True];
Print["Geodesic Closeness: ", 
        N[GeodesicCloseness[graphFig10]]];
Print["Reachability Closeness: ", 
        N[ReachabilityCloseness[graphFig10]]];

\(\(\( (*\ 
 (*The\ following\ code\ imports\ an\ excel\ file\ with\ the\ adjacency\ matrix*) 
SetDirectory["U:\MainDirectory\Research\InstitutionsAndNetworks\IntroductionToFormalAnalysis"]; 
myNetworkMatrix = 
        Import["betweennessNetwork.xls", "XLS"]; 
nNodes = 
        Length[myNetworkMatrix] - 1; 
myAdjMatrix = 
        Round[Take[
            myNetworkMatrix, \(-nNodes\), \(-nNodes\)]]; 
vertexLabels = 
        Rest[myNetworkMatrix[\([1]\)]];
*) \)\(
\)\(
\)\(\(myAdjMatrix = {
{0, 1, 1, 0, 1, 0, 
            0, 0, 0, 0, 0, 0, 0}, {1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 
            0}, {1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 1, 1, 0, 0, 1, 
            0, 1, 0, 0, 0, 0, 0}, {1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
            0}, {0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 1, 
            0, 0, 1, 0, 0, 0, 0}, {0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 
            0}, {0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 
            0, 0, 1, 0, 1, 0, 1}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 
            0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 0, 
            0, 0, 0, 1, 0, 0, 0}};\)

    \(vertexLabels = {"A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M"};\)


    \(graphFig12 = 
        SetVertexLabels[FromAdjacencyMatrix[myAdjMatrix], 
          vertexLabels];\)

    \(ShowGraph[SpringEmbedding[graphFig12]];\)

    Inner[List, vertexLabels, Betweenness[graphFig12], List] // 
      MatrixForm\)\)\)

g = Path[10];
ShowGraph[g, VertexNumber -> True];
Transpose[Inner[List, Range[10], Betweenness[g], List]] // 
      MatrixForm