Hi, RG community! I am new to network analysis and I am currently facing a challenge with coding, processing, and quantifying networks in a hierarchical scheme. In this scheme, nodes pertain to differing hierarchical ranks and ranks denote inclusion relationships. So, for example if node “A” includes node “Z”, it is said that “A” is “Z”’s parent and “Z” is “A”’ daughter. However, a rather uncommon feature is that nodes at different ranks of the hierarchy can relate in a non-inclusive fashion. For example, node “A” parent of “Z” may have a directional link to “Y”, which is “B”’s daughter (if “A” were directionally linked to “B”, then it could be said that “A” is “Y”’ aunt). Here is a more concrete example to illustrate the plausibility of this scheme: “A” is a website in which person “Z” is signed in (inclusiveness; specifically, parentship); website “A” can advertise banners of website “B” (siblingship) or recommend to follow a link to person “Y” profile in website “B” (auntship).
OK. So, in the image below (left top panel) I present a graphical depiction of this rationale. For simplicity, a two-rank hierarchy is used, where gray and red colors denote higher and lower hierarchies, respectively. The image displays siblingship, parentship, and auntship links. My first approach to coding this network scheme was to denote inclusiveness as one-directional relationships (green numbers) and simple links as symmetrical (two-way; brown numbers) relationships (see table in right panel). However, I soon realized that this does not reflect what I expected in networks’ metrics. For example, I am mainly interested in quantifying cohesiveness and the way I coded the network in left top panel entails something like the non-hierarchical network depicted at the left bottom panel. In short, I am not interested in the directionality of the links but in actual inclusiveness. To my mind, the network in the top panel is more cohesive than that in the bottom panel but my coding approach does not allow me to distinguish between them formally.
The solution conceived in the interest of solving this problem was to stipulate that a relationship between any pair of nodes implicates a relationship of each with all of the other’s descendance. This certainly yields, for example, the top network being more cohesive than that in the bottom, which is in line with my goals. However, this solution is not at all as elegant as I would have hoped. Can anyone tell if there is a better solution? Maybe another way to code or an R package allowing for qualitatively distinct relationships (not just one-way or two-way). Thank you.
Instead of listing A/B on the same level (in matrix) as Y etc, what you say you want seems (to me) a graph G = [X,Y,Z,W] with 2 subgraphs A, B.
A simple representation then is a matrix 4x4 and a datastructure to test if a node is in a subgraph or not (dictionary/set).
If you want to model edges between A/B, you can define a new 2x2 matrix describing those.
Note that for large datasets adjacency matrices will scale poorly, so either a adjacency list or sparse matrices can be useful.
There is a fast datastructure for this kind of problem (if A/B are disjoint)
https://en.wikipedia.org/wiki/Disjoint-set_data_structure
If you find you need multiple edges, consider hyper/multigraphs
https://mathworld.wolfram.com/Hypergraph.html
https://mathworld.wolfram.com/Multigraph.html
Hope this helps,
Ben
Here lies the solution to the above-described problem and the underlying rationale is described in my comment to Ben's answer.
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs