# 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
Filter by
Sorted by
Tagged with
1 vote
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, ...
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 ...
29 views

### igraph assortativity by group

The igraph function assortativity_nominal() in R returns a coefficient for the whole graph. ...
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 ...
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 ...
1 vote
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 ...
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 ...
1 vote
25 views

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

Given this network: ...
1 vote
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 ...
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 ...
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 vote
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 ...
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 ...
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 ...
1 vote
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
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 ...
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?
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 ...
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 ...
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 ...
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 ...
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 ...
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
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. ...
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 ...
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 ...
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 vote
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 ...
1 vote
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 ...
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 ...
1 vote
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, ...
1 vote
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 ...
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/...
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 diﬀerence ...
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 ...
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: ...
1 vote
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: <...
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: ...
1 vote
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 ...
1 vote
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,...
1 vote
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 ...
1 vote
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 ...
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 ...
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 ...
1 vote
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 ...