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'.

395 questions
Filter by
Sorted by
Tagged with
298 views

When is multidimensional scaling exact for a graph?

For an undirected graph with one connected component and distance matrix given by the shortest path between nodes, I would like to embed the nodes in a high dimensional Euclidean space where all ...
• 403
115 views

Why are these 2 MAGs Markov Equivalent? DAGs, MAGs, and PAGs

On page 1443 of the linked paper, the authors present the following causal DAG (Directed Acyclic Graph) with a latent variable (Profession). On the following page, they present the 2 MAGs below with ...
• 4,760
4 views

Which variable is best suited for edge weights when computing graph algorithms instead of relative risks?

I am currently trying to develop graph data. Which variable is best suited for edge weights when computing graph algorithms? Relative risk Relative Risk: Many networks in my field use relative risks ...
71 views

Sample a random subgraph from an undirected, unweighted graph, what's the probability of "every two nodes's distance is at least 3 in the subgraph"?

This may be a problem in sampling theory or graph theory. I have done many research but I still didn't find valid solutions. I know a simple random sample is representative of the population. Now I ...
• 295
11 views

Does the weighted Louvain algorithm for maximizing Modularity result in one of the modules containing low weight edges for a fully connected network?

I currently have an implementation of the Louvain Algorithm from the Brain Connectivity Toolbox (BCT) written by Rubinov and Sporns 2010. I was discussing the implementation of it with a professor who ...
• 125
1 vote
46 views

Is there a meaningful way to 'quantify' a group representative partition of its network when subjects within group have their own unique partitions?

I currently have a dataset which can be split into two groups: disease vs control. Each group consists of $n_{disease}$ and $n_{control}$ subjects respectively. The dataset itself is a correlation ...
• 125
1 vote
8 views

Undirected graphs and implications of independence (Wasserman chapter 18)

In Wasserman's All of Statistics chapter 18, he defines the following undirected graph: Let $V$ be a set of random variables with distribution $\mathbb{P}$. Construct a graph with one vertex for each ...
16 views

What is the reason why creating induced subgraphs based on anatomical definitions doesn't seem to be a popular analytical technique?

I was having a discussion with some colleagues about graph theory and how it could be applied to analyzing fMRI datasets, where the matrix is a pairwise correlation matrix between pairs of region of ...
• 125
1 vote
14 views

Correlation of event occurrence in multiple sectors

I have the following problem to analyze: I divided an area into several sectors (i.e.: S1,S2,S3,…,Sn) and there is an event that can happen in one or more sectors at the same time. I considered a ...
• 111
1 vote
76 views

Missing features for nodes in a Graph Neural Network (GNN)

I have built an undirected graph that I want to use to train a binary classifier. The graph represents a network of clients connected through the addresses they used to register. For example, if my ...
• 559
27 views

What is the meaning of graph singal for graph constructed from correlation matrix?

In the highly cited paper "The Emerging Field of Signal Processing on Graphs", the authors defined graph singal for a graph of N vertices as a vector of length N, with each element of the ...
• 227
142 views

Why is Louvain Method Non-Deterministic?

I am using the implementation of the Louvain algorithm for community detection in igraph in R. I observe that running it multiple times produces different answers. However, when I read the algorithm ...
• 2,640
39 views

correct formula for permutation test [duplicate]

in order I need do: measuring the targeted variable on the original network and save it Shuffling my original data (correlation matrix) - randomly (100x) create the graph measuring the targeted ...
1 vote
53 views

• 307
24 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
1 vote
58 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
47 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 ...
151 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,472
453 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 ...
• 121
1 vote
149 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 ...
• 9,412
238 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 ...
• 307
1 vote
30 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
217 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 ...
• 221
1k 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/...
113 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 diﬀerence ...
• 131
63 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
312 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
252 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: <...
1 vote
83 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: ...
• 307
1 vote
200 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 ...
• 1,027
1 vote
141 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,...
• 307
1 vote
286 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 ...
• 910
1 vote
113 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
24 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 ...
• 689