Questions tagged [graph-theory]
Graphs are abstract representations of objects and their mutual relations, where the objects are 'nodes' and the connections among them are 'edges'.
389
questions
1
vote
0
answers
56
views
Comparing centrality measures of different graphs
I have a set of samples that each containing a certain number of points in 2D. The number of points varies across samples. Each point in these samples also has a specific type, like blue, red, green, ...
- 11
0
votes
0
answers
21
views
Graph clustering algorithm for two clusters of same size
I have a graph of 100 nodes. I know that there are 2 clusters of nodes of equal size 50. I created (kind of like a training set) the following instance of the problem (see below, I have some values to ...
0
votes
0
answers
29
views
igraph assortativity by group
The igraph function assortativity_nominal() in R returns a coefficient for the whole graph.
...
- 111
0
votes
0
answers
8
views
Statergies for simulating a hierarchical network using sparsification approaches but mainting global trends
TLDR:
I am trying to simulate a hierarchical network using DFS as a way to sparsify the network. This works to link nodes using edges within the DFS but interactions between nodes are lost. Aside for ...
- 11
0
votes
0
answers
9
views
Mean and variance of number of steps to reach one node from another in random walk on weighted, undirected graph
Suppose I have a connected, undirected graph with edge weights, and I do a random walk over it such that the probability of moving from any node u to one of its neighbors v is equal to the weight of ...
- 123
1
vote
0
answers
17
views
How to start GNN optimization to get higher precision?
I'm developing a GNN for missing links prediction following this blog post for PyG library. I'm using almost the same GNN with a different dataset. Altough my dataset is similar to the MovieLens ...
- 75
3
votes
2
answers
92
views
Probability that two vertices are connected
I'm reading:
Clauset, A., Newman, M.E.J., Moore, C., 2004. Finding community structure in very large networks. Phys. Rev. E 70, 066111. https://doi.org/10.1103/PhysRevE.70.066111
There is written that ...
- 2,040
1
vote
1
answer
25
views
igaph gives me a diameter, but I think the diameter is another one [closed]
Given this network:
...
- 2,040
1
vote
1
answer
49
views
Calculating modularity gain of switching a node from one community to another (Louvain algorithm)
I am trying to implement the Louvain algorithm in PySpark.
An important part of the algorithm involves calculating the modularity gain of taking node $i$ out of its current community $C_0$ and placing ...
- 443
0
votes
0
answers
12
views
Balanced Graph Communities With Node Weights
I'm looking for where best to start on the following problem.
I have a graph of N nodes and each node as a weight. I need to group all nodes into X groups such that the sum of weights in each group ...
0
votes
0
answers
30
views
Given a graph representing a NPSEM-IE, how can I show that another graph also represents one?
Good morning,
I am currently following a class on Biostatistics and am currently struggling on an exercise. I am given 2 graphs $G1$ and $G2$.
Then, assuming that $G1$ represents a NPSEM-IE, I have to ...
- 1
1
vote
1
answer
37
views
Is there a theory for estimating "node differences" using "edge samples" over graph
Assume a system consisting of several components. Each component is characterized by some real number.
A sample of a pair of components in the system, is a random variable normally distributed around ...
- 13
0
votes
0
answers
10
views
How can I create a similarity network from a point cloud in vector space for classification purposes?
Are there any relevant techniques or approaches, such as k-nn graph or feature combination, that could be used to establish a similarity distance to create a graph to be used for gnn node ...
- 333
2
votes
1
answer
90
views
What is an inducing path in causal inference?
In causal graphical models, an inducing path is defined as:
[Definition Inducing Path] An inducing path relative to L is a path on which every non-endpoint node ...
- 255
1
vote
0
answers
27
views
What is the suitable Graph Machine Learning model for dynamic graph forecasting with changing nodes and edges features
I have a graph where each node carries a feature value(s). The edges in the graph are weighted and each edge carries a single value (weight). The weight of the edge is some value calculated using the ...
1
vote
0
answers
34
views
Comparing sets of overlapping correlations
I have a data set of N samples (>10k) and expression measurements for P genes. Among the P genes, there are subsets Ptf (795 genes) and Ptarget (2492 genes) that form a bipartite graph. Not all ...
- 11
0
votes
0
answers
10
views
solving simple MRF problem with graph-cut
I'm trying to solve this simple question with graph cut:
I draw the graph and I get that that all pixel label sould be 1 while 000 is minimizing E,
what did I missed?
2
votes
1
answer
49
views
What is a "directed path" in context of causal graphs?
I am going through Causal Inference In Statistics by Pearl and I have come across the definition of path and directed path (section 1.4, page 25).
Path: A path between two nodes $X$ and $Y$ is a ...
10
votes
1
answer
365
views
Are there algorithms to cluster Graphs, not just cluster nodes in a graph?
I am wondering if there are algorithms to cluster graphs; what I meant is to cluster many graphs, not cluster the nodes in a graph.
For example, we have N graphs, G1, G2, G3, .....GN. Then we can ...
- 357
3
votes
1
answer
268
views
Where does the normalization constant of betweenness centrality come from?
As stated by Wikipedia, the betweenness centrality of a node $v$ is given by the expression:
$$g(v)=\sum _{{s\neq v\neq t}}{\frac {\sigma _{{st}}(v)}{\sigma _{{st}}}}$$
where $\sigma_{st}$ is the ...
- 297
0
votes
0
answers
22
views
Significant changes in short time series from a multilevel graph
I have a multilevel weighted graph $G=\{G_t, \forall t=1,\ldots,6\}$ in which each level $G_t$ represents a given year. For some of the nodes each year, $V_{t,j}, \in G_t$, I calculated the proportion ...
- 11
0
votes
0
answers
21
views
Vapnik-Chervonenkis dimension of hypergraph, given bound on number of hyperedges
in studying now about Vapnik-Chervonenkis dimension, and there is one question that I not able to solve.
Let $\textrm{(X , R)}$ be a range space so that any hypergraph $\textrm{(V, F)}$ in it ...
- 1
0
votes
0
answers
86
views
Personalized PageRank and Random Walks
I have 2 questions.
First, the equation for personalized PageRank from here is
pi_s = a * e_s + (1-a) * R * pi_s
where pi_s is ...
1
vote
0
answers
47
views
Relations between clustering, graph-theory and principal components
I am trying to give some theoretical foundations to the intuitive idea that three branches of mathematics are indeed tightly connected, specifically: clustering, graph-theory and principal components.
...
- 63
4
votes
2
answers
46
views
Why Deep Learning needs to be performed in Graphical representations?
Why do we bother about devising new Deep Learning methods, which is to be applied on graphical representation of data? Why not use the traditional Deep Learning methods in the adjacency matrix ...
0
votes
0
answers
12
views
Depth first search heuristic for large graph with very uneven distribution in terms of vertex's connections
Problem Context:
I need to perform Depth first search on a large graph (think 50k Edges & 10K vertices) under 500MS latency constraint.
The graph has the special property where the connections ...
2
votes
1
answer
103
views
How to interpret the minimum spanning tree in a fully-connected graph?
Can someone explain how the resulting graph is the minimum spanning tree (MST) from the fully-connected undirected graph? I don't understand how this is interpreted in this context.
Definition ...
- 1,422
1
vote
0
answers
255
views
Predict unseen samples with Graph Neural Networks
I am recently studying graph neural networks (GNNs). I have read some papers, e.g., Semi-Supervised Classification with Graph Convolutional Networks, and blogs, e.g., Training Graph Convolutional ...
- 111
1
vote
0
answers
131
views
Embedded minimum spanning trees for visualizing effects of dimensionality reduction?
Gist
Construct a minimum spanning tree (MST) of the data, perform a dimensionality reduction procedure, and plot the embedding MST to study a "skeleton" of the transformed data.
Mathematical ...
- 6,988
4
votes
1
answer
136
views
sigma-separation question in cyclic causal graph - understanding sigma-separation
Main Question
In https://arxiv.org/pdf/1807.03024.pdf, a generalization of d-separation in DAGs is introduced, called $\sigma$-separation for cyclic graphs.
I am wondering how $v_1 \perp v_6$ using ...
- 255
1
vote
0
answers
24
views
How can I model or estimate the probability of a given network connection in a bipartite graph of relationships that may or may not exist?
I have a large set of network data, with many groups. Within each group, there are some criteria for creating "candidate" relationships between entities.
Below I have an example of 8 groups, ...
- 418
1
vote
0
answers
155
views
Exponential Random Graph Model Implementation Python, Error [closed]
So I am trying to implement the most basic Exponential Random Graph Model implementation using Python. Concretely I'm trying to estimate the maximum pseudo likelihood estimate, which can be formulated ...
- 211
3
votes
1
answer
619
views
Difference between Symmetrically normalized Laplacian matrix versus graph laplacian matrix
I am trying to understand the graph laplacian matrix in Graph Convolution networks.
To get a basic understanding of graph laplacian matrix I am referring to this
https://mbernste.github.io/posts/...
- 244
2
votes
1
answer
82
views
Why are undirected graphical models (MRFs) not represented directly in terms of probability like directed graph models?
I have been reading the Deep Learning Book by Ian Goodfellow, and in that, there is a discussion about graphical models like Bayesian belief networks and Markov Random Fields. Here:
One key difference ...
- 131
0
votes
1
answer
50
views
Probability of player being selected at each draft order
Problem
A set of 26 people (person A, B, ..., Z) play pick-up soccer 100+ times. Each time ...
- 163
2
votes
0
answers
207
views
Is normalizing input graph's node attributes before training GNNs required? How to do it
I am new in GNN, and I have a dataset of weighted graphs that each node in each graph has the following attributes:
...
- 21
1
vote
0
answers
171
views
Graph Convolutional Network work badly: my accuracy doesn’t grow!
I’m trying to classify some drugs like very active, active, non active (label: 0, 1, 2) against the cancer. To do that I built a Graph Convolutional Network using PyTorch Geometric, this is the code:
<...
0
votes
1
answer
49
views
Why is the closeness centrality value higher for less connected nodes?
I built an igraph graph from a data frame containing the (symbolic) edge list and weight. This is the data frame:
...
- 297
1
vote
0
answers
152
views
How to handle missing data when calculating network homophily/assortativity?
I am trying to calculate network homophily/assortativity for a graph. However, some of my nodes have missing values. It turns out igraph's assortativity functions have no "na.rm" function ...
- 525
1
vote
0
answers
124
views
Parents in a directed acyclic graph vs a partial ancestral graph
In DAGs, parents are defined as follows:
A is a parent of B if 'A -> B' edge is in the graph.
In PAGs, there are mixed type of edges, so you can have A -> B, A o-> B. Obviously if A -> B,...
- 255
1
vote
0
answers
197
views
List of algorithms used to cluster weighted undirected graphs
What clustering methods are suitable for weighted graphs, where the weights cannot be interpreted as a metric ? (e.g. they do not respect the triangle inequality). At the moment I found Markov ...
- 840
1
vote
0
answers
77
views
What metrics can be used to measure the difference in connectivity between graphs?
I have two sets of weighted and directed graphs with the same nodes. I expect that between these two families there is a variation in connectivity driven by some phenomenon. How could I highlight this ...
- 23
2
votes
0
answers
22
views
Spatial crosscorrelation between a binary and continuous measurement on a graph
I have a graph $G$ with vertex set $V$ and edge set $E$. I measure two signals on the vertices of the graph $X$ and $Y$.
If $X$ and $Y$ are both continuous, we can measure spatial crosscorrelations ...
- 669
2
votes
0
answers
73
views
Algorithm to check if there is an inducing path between two nodes - constructing maximal ancestral graph (MAG) given a DAG
In causal inference, one generally learns a Markov equivalence class of causal graphs when trying to reconstruct causal structure from data. This is known as a maximal ancestral graph (MAG).
I am ...
- 255
1
vote
1
answer
230
views
Why do I even need DeepWalk and Node2Vec when I can build a visual graph structure?
While studying DeepWalk, I started wondering why I need "DeepWalk" when I can build a graph from data and visualize the structure of a graph. With a visualized graph, I can see which nodes ...
- 3,145
0
votes
1
answer
114
views
TSP (Travel Salesman problem) for multigraph
I'm trying to solve the Travel Salesman problem for multigraph.
Namely, I have a fully-connected graph with 2 oriented edges between every pair of nodes. The weight of the edge from x to y corresponds ...
- 1
5
votes
1
answer
141
views
Intuition and meaning of a "discriminating path" in a causal DAG
In Ali, Richardson and Spirtes (2009) (open copy here) and many other papers in the causal DAG literature, there is the notion of a "discriminating path". The definition is:
A path $\pi = ⟨...
- 255
4
votes
1
answer
908
views
Weighted adjacency matrix normalization for GCN, how to normalize? what about self-loop values?
I am implementing a GCN that will work on a weighted graph. The edges' weights are in the range [1, 250]. When it comes to normalizing the adjacency matrix for GCNs, the standard formula of a ...
- 358
3
votes
2
answers
1k
views
Nodes' attribute scaling/normalization before graph embedding learning - GNN?
In a node classification setting, is it require to normalize/scale graph node attributes before learning node embeddings using graph neural networks? Why?
- 358
1
vote
0
answers
49
views
Marginal Distribution of a Stochastic Block Model?
Let us say I have a Stochastic Block Model i.e. a random vector $X^{(n)} = [x_1,...,x_n]$ where $P(x_i = c) = P_{c}$, where $c \in \{1,...,u\}$, and a random simple undirected graph represented by $Y^{...
- 151