how to find neighbors/degree of hyperedges of a uniform hypergraph?

2 views (last 30 days)
I have data set of 10 uniform hyperedges:
T=[1 6 12; 2 6 13; 3 7 12; 4 7 14; 4 7 15; 1 8 16; 2 9 16; 4 8 17; 5 10 13; 1 11 18];
Now, I have to find degree and neighbors of hyperedge. For ex. first edge (1 6 12) have degree 4 and neighbors are hyperedge 2,3,6,10.
I made this code but it is computationally expensive for large data set.
Can we use another approach whose complexity is linear?
T=[1 6 12; 2 6 13; 3 7 12; 4 7 14; 4 7 15; 1 8 16; 2 9 16; 4 8 17; 5 10 13; 1 11 18];
[A,B,C]=deal(T(:,1),T(:,2),T(:,3));
for i=1:size(T,1)
p=T(i,:);
[a,b,c]=deal(p(1),p(2),p(3));
D=[];
%to find degree(da) by searching adjacent hyperedges of p in T
D=[D,find(A'==a)];
D=[D,find(B'==b)];
D=[D,find(C'==c)];
D=unique(D);
da=[da,size(D,2)-1];
end

Accepted Answer

Christine Tobler
Christine Tobler on 24 Jun 2023
Edited: Christine Tobler on 26 Jun 2023
MATLAB doesn't support hypergraphs, but often a specific problem can be solved with just a graph or multigraph, by interpreting the hyperedges as additional nodes. In this case, we can construct a simple graph where each node represents a hyperedge of the hypergraph, and there is an edge connecting any pair of nodes of the respective hyperedges share a node:
T=[1 6 12; 2 6 13; 3 7 12; 4 7 14; 4 7 15; 1 8 16; 2 9 16; 4 8 17; 5 10 13; 1 11 18];
% Matrix M where M(i, j) = 1 if hyperedge i contains node j.
M = sparse(repmat((1:10)', 1, 3), T, 1);
% Matrix A where A(i, j) >= 1 if hyperedges i and j share at least one node.
A = M*M';
% Make a graph where each node represents a hyperedge
g = graph(M*M', 'omitselfloops');
plot(g)
% Neighbors of hyperedge 1, as expected:
neighbors(g, 1)'
ans = 1×4
2 3 6 10
% Degree of each hyperedge, corresponds to da in original post
degree(g)'
ans = 1×10
4 3 3 3 3 4 2 3 1 2
% By the way, to make a plot of the hypergraph (not just the reinterpration
% above), make a graph where the first 10 nodes represent the hyperedges,
% and the following 18 nodes represent the nodes.
g = graph([sparse(10, 10), M; M', sparse(18, 18)]);
% Then, plot and turn off the markers on the hyperedges:
p = plot(g);
highlight(p, 1:10, Marker="none", NodeLabelColor=[0 0.8 0])
  4 Comments
Urvashi
Urvashi on 29 Jun 2023
I used +1 thing but the problem is that resulted Matrix entries is not unique w.r.t each column. So M has 8*6 dimension, and it isn't the desired matrix. To solve this problem, I thought to convert t into
T=[1 7 11; 1 8 12; 2 7 13; 3 9 13; 4 9 14; 5 10 11; 5 11 15; 6 10 16] By checking each column of t (row wise) and respectively give unique entries to T, but this will take 2 loops and several steps for checking.
Can we do it through vectorization? to reduce complexity.
Or can this be done through other approach?
Christine Tobler
Christine Tobler on 30 Jun 2023
Edited: Christine Tobler on 30 Jun 2023
Sorry, I didn't look at the matrix T carefully enough initially - I hadn't noticed that it has multiple identical nodes in some of the hyperedges.
The code above will treat this as being a hyperedge that only connects to each node once - am I right to assume you would like this to be treated as still a hyperedge with 3 nodes? That is, the hyperedge [1 1 1] will mean the degree of node 1 is 3?
Say I have a set of hyperedges defined by T = [1 1 1; 1 1 2], what would the degree of these hyperedges be? Do they both have degree 6, because there are 6 combinations of moving from hyperedge 1 through node 1 to hyperedge 2? Or just degree 1, because there is only 1 unique hyperedge that is their direct neighbor?
If what you are looking for in the above example is degree 6, I believe the following modification of the code above will work:
T=[0 0 0; 0 1 1; 1 0 2; 2 2 2; 3 2 3; 4 3 0; 4 4 4; 5 3 5] + 1;
e = size(T, 1);
% Matrix M where M(i, j) = 1 if hyperedge i contains node j.
M = sparse(repmat((1:e)', 1, size(T, 2)), T, 1);
% Matrix A where A(i, j) >= 1 if hyperedges i and j share at least one node.
A = M*M';
% Make a graph where each node represents a hyperedge
g = graph(M*M', 'omitselfloops');
plot(g, EdgeLabel=g.Edges.Weight) % weights show number of connections
degreeCountingMultiples = full(sum(adjacency(g, 'weighted')))
degreeCountingMultiples = 1×8
9 7 11 6 8 11 3 3
And here's again a plot that shows both the nodes and the hyperedges of this graph
n = size(M, 2); % number of nodes
gBoth = graph(repmat((1:e)', 1, size(T, 2))+n, T);
% Then, plot and turn off the markers on the hyperedges:
p = plot(gBoth);
highlight(p, n+1:n+e, Marker="none", NodeLabelColor=[0 0.8 0])
labelnode(p, n+1:n+e, 1:e)

Sign in to comment.

More Answers (0)

Categories

Find more on Graph and Network Algorithms in Help Center and File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!