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

363 questions
Filter by
Sorted by
Tagged with
9 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: ...
• 187
12 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 ...
• 309
1 vote
9 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,...
• 153
1 vote
48 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 ...
• 663
1 vote
20 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
17 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 ...
• 639
42 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 ...
• 153
31 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 ...
• 2,583
36 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 ...
71 views

• 151
1 vote
35 views

### Graph Classification via Random Forest

This is my first post here, just a brief presentation: my name is Gianmarco, I’m Medicinal Chemistry undergraduate student who is preparing his dissertation, my idea would be to create a classifier ...
15 views

### Getting two probability distributions over graphs to agree on the probability of a given graph?

I have a simple fully connected graph with $N$ nodes and hence $\binom{N}{2}$ edges. I am asked to colour this fully connected graph, where I pick the colour for the nodes w.r.t a Multinomial ...
• 151
79 views

### How to Cluster Several Graphs?

I'm relatively new to Graph Theory, but I'm wondering if I have a set of Graphs {G1, G2, ..., Gn}, are there any algorithms that allow for clustering these graphs? taking into account the nodes and ...
• 131
1 vote
7 views

### Associate prediction task to a graph autoencoder (GAE)

I have been reading about graph autoencoders and was wondering if it might be a reasonable idea trying to associate to the unsupervised setting which produces some best low-dimensional representation ...
• 427
1 vote
11 views

### Comparing properties of networks of different sizes

I want to compare some network properties such as density, average path and modularity among groups of sizes ranging from 100 to 4000. How can I correctly compare these networks? Considering the ...
1 vote
13 views

### Proof for a seemingly simple property for fully-connected coloured random graphs?

I have a probability distribution defined over a set of fully-connected simple graphs depending on their coloring. Let us have a fully connected graph with $N$ nodes, a node may have a color $i$ ...
• 151
26 views

### Passing entire dataset into convolution layer when training?

So for some context, I have been building my own computation graph to model the way PyTorch and Tensorflow build their machine learning frameworks. I have recently finished implementing the ...
32 views

### How to identify number of vertices, edges and weights in a cellular network

Suppose we have a cellular network then what are the vertices, edges and edges weights in this network. I have choose customers as vertices. Customers calling each other as edges. Time of duration ...
32 views

### Data association on data from multiple cameras

Suppose we have several cameras that cover a certain area. In each camera we track a person. Each person have a path in global coordinates, timestamps and a feature-vector. The goal is to group these ...
1 vote
34 views

### Are graphical neural networks the right approach for isomorphic graphs?

I have a set of $N$ observations ($N>100,000$): each observation takes the form of a homogeneous, undirected graph $G_n=(V,E)$ all graphs $G_n$ have the same nodes and edges - around 5,000 nodes ...
18 views

### Hyperparameter selection in Affinity Propagation without ground truth

My goal is to implement affinity propagation for clustering a given dataset (n=12 features), and I wish to find the optimal hyperparameter value (preference) allowing an educated guess of the number ...
• 11
11 views

• 21
49 views

### Gaussian process regression on a graph

I am looking for a way to do Gaussian process regression on a weighted graph. Analogously to the prototypical GPR plot, I made a drawing to make it more clear: The filled nodes have a training point ...
• 444
1 vote