3
$\begingroup$

I'm trying to work out how to identify both the mean and median number of links attached to neighboring nodes when iterating through nodes A1 to B5. Below I have an example matrix, given as matrixlist, it's visualization, given as matrixvisualization and the corresponding adjacency graph, graph:

matrixlist = {{1, 1, 0, 0, 0, 0, 1, 0, 0, 0}, {1, 0, 0, 0, 1, 1, 0, 0,
    1, 0}, {0, 0, 0, 0, 1, 1, 0, 0, 0, 1}, {0, 0, 0, 0, 0, 0, 0, 0, 0,
    0}, {0, 1, 1, 0, 0, 0, 0, 0, 1, 1}, {0, 1, 1, 0, 0, 0, 1, 0, 0, 
   1}, {1, 0, 0, 0, 0, 1, 0, 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, 1, 0, 1, 1, 0, 0, 0, 0}}

matrixvisualization = MatrixForm[matrixlist, 
 TableHeadings -> {{"A1", "A2", "A3", "A4", "A5", "B1", "B2", "B3", 
    "B4", "B5"}, {"A1", "A2", "A3", "A4", "A5", "B1", "B2", "B3", 
    "B4", "B5"}}]

graph = AdjacencyGraph[verticeLabel, matrixlist,  
  VertexLabels -> Placed["Name", Center],
  VertexSize -> .8,
  VertexStyle -> White]

I've included a picture of the graph to help with the explanation of what I'm trying to obtain. I would like to figure out how to find the mean number of links off neighboring nodes for each of the nodes present in the graph.

For example, in the graph provided, node A1 has two neighbors, A2 and B2. A2 has a total of 4 links off of it and B2 has two links. Therefore, the mean number of links off neighboring nodes with respect to A1is 3. Taking the same idea and applying it to the next node sequentially, A2, the mean number of links off neighboring nodes with respect to A2 would be 3.25 (Loops are only counted as 1 additional link so A1 has 3 links in total). I would like to repeat this process for each node in the graph and then create a list which contains the averages.

meannewlist = {3, 3.25 ...}

Taking the same process above, I'm also trying to find out the medium number of links off neighboring nodes for each node. For example if we start at A1, the median number of neighboring links with respect to A1 is 3 (coincidentally the same as its average number found above). As mentioned above, I would like to list all the median values in a list:

 mediannewlist = {3, 3.25...}

Any insight as to how I might solve this would be greatly appreciated.

enter image description here

$\endgroup$
2
$\begingroup$

Update: We can use AdjacencyList to define a function to apply an arbitrary function to an arbitrary property value of neighbors:

ClearAll[neighborPropertyMap]
neighborPropertyMap[foo_: Identity, property_: VertexDegree][g_] := 
 ReplaceAll[foo[{}] -> {}] @* foo @*
   Map[(property /. Identity -> (#2 &))[g, #] &] /@ AdjacencyList[g]

Examples:

simplegraph = SimpleGraph[graph, Options @ graph]

List of neighbors' degrees:

neighborPropertyMap[] @ simplegraph
{{4, 2}, {2, 4, 4, 2}, {4, 4, 3}, {}, {4, 3, 2, 3}, {4, 3, 2, 3}, {2, 4},
 {}, {4, 4}, {3, 4, 4}}

Mean of neighbor degrees:

neighborPropertyMap[Mean] @ simplegraph
{3, 3, 11/3, {}, 3, 3, 3, {}, 4, 11/3}

Variance of neighbor degrees:

neighborPropertyMap[Variance] @ simplegraph
{2, 4/3, 1/3, {}, 2/3, 2/3, 2, {}, 0, 1/3}

Median:

neighborPropertyMap[Median] @ simplegraph
{3, 3, 4, {}, 3, 3, 3, {}, 4, 4}

MinMax:

neighborPropertyMap[MinMax] @ simplegraph
{{2, 4}, {2, 4}, {3, 4}, {}, {2, 4}, {2, 4}, {2, 4}, {}, {4, 4}, {3, 
  4}}

List of neighbors:

neighborPropertyMap[Identity, Identity] @ simplegraph
{{"A2", "B2"}, {"A1", "A5", "B1", "B4"}, {"A5", "B1", 
  "B5"}, {}, {"A2", "A3", "B4", "B5"}, {"A2", "A3", "B2", 
  "B5"}, {"A1", "B1"}, {}, {"A2", "A5"}, {"A3", "A5", "B1"}}

VertexWeight's of neighbors:

SeedRandom[77]
simplegraph2 = SetProperty[simplegraph, VertexWeight -> {v_ :> RandomInteger[{1, 100}]}];

neighborPropertyMap[Identity, PropertyValue[{#, #2}, VertexWeight] &]@simplegraph2
{{8, 88}, {1, 52, 63, 79}, {52, 63, 77}, {}, {8, 88, 79, 77}, 
  {8, 88, 88, 77}, {1, 63}, {}, {8, 52}, {88, 52, 63}}
neighborPropertyMap[N@*Mean, PropertyValue[{#, #2}, VertexWeight] &]@simplegraph2
 {48., 48.75, 64., {}, 63., 65.25, 32., {}, 30., 67.6667}

VertexStyle's of neighbors:

SeedRandom[123]
simplegraph3 = SetProperty[simplegraph, VertexStyle -> {v_ :> RandomColor[]}];

neighborPropertyMap[Identity, PropertyValue[{#, #2}, VertexStyle] &]@simplegraph3

enter image description here

neighborPropertyMap[Lighter@*Lighter, PropertyValue[{#, #2}, VertexStyle] &]@simplegraph3

enter image description here

neighborPropertyMap[Blend, PropertyValue[{#, #2}, VertexStyle] &]@simplegraph3

enter image description here

Original answer:

Remove the self-loops from graph:

simplegraph = SimpleGraph[graph, Options @ graph]

enter image description here

Get an Association associating each vertex with its neighbors:

neighborsList =  AssociationThread[VertexList[simplegraph], 
  AdjacencyList[simplegraph]]
<|"A1" -> {"A2", "B2"}, "A2" -> {"A1", "A5", "B1", "B4"}, 
  "A3" -> {"A5", "B1", "B5"}, "A4" -> {}, 
  "A5" -> {"A2", "A3", "B4", "B5"}, "B1" -> {"A2", "A3", "B2", "B5"}, 
  "B2" -> {"A1", "B1"}, "B3" -> {}, "B4" -> {"A2", "A5"}, 
  "B5" -> {"A3", "A5", "B1"}|>

Map VertexDegree on neighborsList to get an Association linking each vertex to the list of vertex degrees of its neighbors:

neighborDegrees = Map[VertexDegree[simplegraph, #] &] /@ neighborsList
<|"A1" -> {4, 2}, "A2" -> {2, 4, 4, 2}, "A3" -> {4, 4, 3}, "A4" -> {},
  "A5" -> {4, 3, 2, 3}, "B1" -> {4, 3, 2, 3}, "B2" -> {2, 4}, 
  "B3" -> {}, "B4" -> {4, 4}, "B5" -> {3, 4, 4}|>

Alternatively, map Length @* neighborsList on neighborsList (number of neighbors of each neighbor):

Map[Length @* neighborsList] /@ neighborsList == neighborDegrees
True

Now map any function you like to the association values:

foo /@ neighborDegrees
<|"A1" -> foo[{4, 2}], "A2" -> foo[{2, 4, 4, 2}], 
  "A3" -> foo[{4, 4, 3}], "A4" -> foo[{}], "A5" -> foo[{4, 3, 2, 3}], 
  "B1" -> foo[{4, 3, 2, 3}], "B2" -> foo[{2, 4}], "B3" -> foo[{}], 
  "B4" -> foo[{4, 4}], "B5" -> foo[{3, 4, 4}]|>
If[# === {}, {}, Median@#] & /@ neighborDegrees
<|"A1" -> 3, "A2" -> 3, "A3" -> 4, "A4" -> {}, "A5" -> 3, "B1" -> 3, 
 "B2" -> 3, "B3" -> {}, "B4" -> 4, "B5" -> 4|>
Values @ %
 {3, 3, 4, {}, 3, 3, 3, {}, 4, 4}
If[# === {}, {}, Mean@#] & /@ neighborDegrees
<|"A1" -> 3, "A2" -> 3, "A3" -> 11/3, "A4" -> {}, "A5" -> 3, 
  "B1" -> 3, "B2" -> 3, "B3" -> {}, "B4" -> 4, "B5" -> 11/3|>
Values @ %
{3, 3, 11/3, {}, 3, 3, 3, {}, 4, 11/3}
$\endgroup$
1
$\begingroup$

You can work directly with the input matrix

  1. Construct a SparseArray from matrixlist
  2. Use SparseArray`SparseArrayRemoveDiagonal to remove the diagonal
  3. Take the property "AdjacencyLists"
  4. Use MapIndexed + Association to get an association associating each vertex index to the indices of adjacent vertices

nL = Association @
      MapIndexed[#2[[1]] -> # &] @
       SparseArray`SparseArrayRemoveDiagonal[SparseArray @ matrixlist] @
       "AdjacencyLists"
 <|1 -> {2, 7}, 2 -> {1, 5, 6, 9}, 3 -> {5, 6, 10}, 4 -> {}, 
   5 -> {2, 3, 9, 10}, 6 -> {2, 3, 7, 10}, 7 -> {1, 6}, 8 -> {}, 
   9 -> {2, 5}, 10 -> {3, 5, 6}|>

Map Length @* nL on nL (get the neighbor counts of neighbors):

nD = Map[Length @* nL] /@ nL
<|1 -> {4, 2}, 2 -> {2, 4, 4, 2}, 3 -> {4, 4, 3}, 4 -> {}, 
 5 -> {4, 3, 2, 3}, 6 -> {4, 3, 2, 3}, 7 -> {2, 4}, 8 -> {}, 
 9 -> {4, 4}, 10 -> {3, 4, 4}|>

Map any function you desire on nD:

foo /@ nD
<|1 -> foo[{4, 2}], 2 -> foo[{2, 4, 4, 2}], 3 -> foo[{4, 4, 3}], 
 4 -> foo[{}], 5 -> foo[{4, 3, 2, 3}], 6 -> foo[{4, 3, 2, 3}], 
 7 -> foo[{2, 4}], 8 -> foo[{}], 9 -> foo[{4, 4}], 
 10 -> foo[{3, 4, 4}]|>
Mean /@ nD /. Mean[{}] -> {}
<|1 -> 3, 2 -> 3, 3 -> 11/3, 4 -> {}, 5 -> 3, 6 -> 3, 7 -> 3, 8 -> {},
  9 -> 4, 10 -> 11/3|>
Median /@ nD /. Median[{}] -> {}
<|1 -> 3, 2 -> 3, 3 -> 4, 4 -> {}, 5 -> 3, 6 -> 3, 7 -> 3, 8 -> {}, 
 9 -> 4, 10 -> 4|>

If you desire, you can replace key i with verticeLabel[[i]] in nD

nD2 = KeyMap[verticeLabel[[#]] &]@nD
<|"A1" -> {4, 2}, "A2" -> {2, 4, 4, 2}, "A3" -> {4, 4, 3}, "A4" -> {},
  "A5" -> {4, 3, 2, 3}, "B1" -> {4, 3, 2, 3}, "B2" -> {2, 4}, 
  "B3" -> {}, "B4" -> {4, 4}, "B5" -> {3, 4, 4}|>
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.