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

3 次查看（过去 30 天）
Urvashi
Urvashi 2023-6-24
编辑： Christine Tobler 2023-6-30
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

请先登录，再回答此问题。

采纳的回答

Christine Tobler
Christine Tobler 2023-6-24
编辑：Christine Tobler 2023-6-26
Ran in:
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 个评论
显示 2更早的评论
Urvashi
Urvashi 2023-6-29
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 2023-6-30
编辑：Christine Tobler 2023-6-30
Ran in:
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)

请先登录，再进行评论。

更多回答（0 个）

类别

在 Help Center 和 File Exchange 中查找有关 Graph and Network Algorithms 的更多信息

标签

Community Treasure Hunt

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

Start Hunting!

Translated by