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

3 visualizzazioni (ultimi 30 giorni)
Urvashi il 24 Giu 2023
Modificato: Christine Tobler il 30 Giu 2023
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
##### 0 CommentiMostra -2 commenti meno recentiNascondi -2 commenti meno recenti

Accedi per commentare.

### Risposta accettata

Christine Tobler il 24 Giu 2023
Modificato: Christine Tobler il 26 Giu 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 CommentiMostra 2 commenti meno recentiNascondi 2 commenti meno recenti
Urvashi il 29 Giu 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 il 30 Giu 2023
Modificato: Christine Tobler il 30 Giu 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 = 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)

Accedi per commentare.

### Categorie

Scopri di più su Graph and Network Algorithms in Help Center e File Exchange

### Community Treasure Hunt

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

Start Hunting!

Translated by