Skip to main content

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

Filter by
Sorted by
Tagged with
4 votes
2 answers
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 ...
user3433489's user avatar
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 ...
ColorStatistics's user avatar
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 ...
user1190107's user avatar
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 ...
Voyager's user avatar
  • 295
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 ...
Syuma's user avatar
  • 125
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 ...
Syuma's user avatar
  • 125
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 ...
NovicePatience's user avatar
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 ...
Syuma's user avatar
  • 125
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 ...
Rodrigo's user avatar
  • 111
1 vote
1 answer
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 ...
Arturo Sbr's user avatar
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 ...
Patrick's user avatar
  • 227
4 votes
1 answer
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 ...
G5W's user avatar
  • 2,640
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 ...
Ana Paula Castro's user avatar
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)), \...
Finn R's user avatar
  • 11
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 ...
roymustang's user avatar
1 vote
0 answers
78 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, ...
user178882's user avatar
0 votes
0 answers
33 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 ...
Jin Kazama's user avatar
1 vote
0 answers
24 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 ...
James's user avatar
  • 135
3 votes
2 answers
191 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 ...
robertspierre's user avatar
1 vote
1 answer
41 views

igaph gives me a diameter, but I think the diameter is another one [closed]

Given this network: ...
robertspierre's user avatar
2 votes
1 answer
177 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 ...
Arturo Sbr's user avatar
1 vote
0 answers
15 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 ...
Lee Phillips's user avatar
1 vote
1 answer
38 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 ...
yonayaha's user avatar
4 votes
1 answer
226 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 ...
ajl123's user avatar
  • 307
1 vote
0 answers
37 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 ...
Traveling Salesman's user avatar
1 vote
0 answers
45 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 ...
mrkevomeli's user avatar
7 votes
2 answers
186 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 ...
Anirban Chakraborty's user avatar
10 votes
1 answer
405 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 ...
TripleH's user avatar
  • 377
3 votes
1 answer
608 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 ...
Mark's user avatar
  • 307
0 votes
0 answers
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 ...
lsu's user avatar
  • 1
1 vote
0 answers
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. ...
Vitomir's user avatar
  • 63
4 votes
2 answers
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 ...
Hari Krishnan U's user avatar
2 votes
1 answer
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 ...
O.rka's user avatar
  • 1,472
2 votes
1 answer
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 ...
CLRW97's user avatar
  • 121
1 vote
0 answers
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 ...
Galen's user avatar
  • 9,412
4 votes
1 answer
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 ...
ajl123's user avatar
  • 307
1 vote
0 answers
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, ...
Max Candocia's user avatar
1 vote
0 answers
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 ...
user2550228's user avatar
5 votes
1 answer
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/...
Jose_Peeterson's user avatar
2 votes
1 answer
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 difference ...
Kunj Mehta's user avatar
0 votes
1 answer
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 ...
azizj's user avatar
  • 163
2 votes
0 answers
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: ...
meee's user avatar
  • 21
1 vote
0 answers
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: <...
Gianmarco Luchetti 's user avatar
1 vote
1 answer
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: ...
Mark's user avatar
  • 307
1 vote
0 answers
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 ...
JElder's user avatar
  • 1,027
1 vote
0 answers
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,...
ajl123's user avatar
  • 307
1 vote
0 answers
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 ...
Thomas's user avatar
  • 910
1 vote
0 answers
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 ...
Davide's user avatar
  • 23
2 votes
0 answers
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 ...
Devil's user avatar
  • 689
2 votes
0 answers
90 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 ...
ajl123's user avatar
  • 307

1
2 3 4 5
8