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
4
votes
2
answers
297
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 ...
5
votes
1
answer
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 ...
0
votes
0
answers
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 ...
2
votes
1
answer
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 ...
0
votes
0
answers
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 ...
1
vote
1
answer
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 ...
1
vote
0
answers
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 ...
0
votes
0
answers
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 ...
1
vote
0
answers
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 ...
1
vote
1
answer
74
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 ...
0
votes
0
answers
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 ...
4
votes
1
answer
141
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
...
0
votes
0
answers
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
0
answers
53
views
Expected steps until collision of a simultaneous walk in two random functional graphs
Let $f$ be a function $f : \{0, 1, 2, \dots, n - 1\} \to \{0, 1, 2, \dots, n - 1\}$. Now let $u \in \{0, 1, 2, \dots, n - 1\}$. $u$ is our initial value. Consider the sequence
$$
u, f(u), f(f(u)), \...
0
votes
0
answers
22
views
Can Convolutional Neural Networks (CNNs) be accurately represented as directed acyclic graphs (DAGs)?
While it's evident that fully connected layers, even with skip connections, form DAGs, the shared weights in convolutional layers introduce complexity. How does the unique structure of convolutional ...