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
0 votes
0 answers
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: ...
user avatar
  • 187
0 votes
0 answers
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 ...
user avatar
  • 309
1 vote
0 answers
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,...
user avatar
  • 153
1 vote
0 answers
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 ...
user avatar
  • 663
1 vote
0 answers
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 ...
user avatar
  • 23
2 votes
0 answers
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 ...
user avatar
  • 639
2 votes
0 answers
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 ...
user avatar
  • 153
0 votes
1 answer
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 ...
user avatar
  • 2,583
0 votes
0 answers
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 ...
user avatar
  • 1
5 votes
1 answer
71 views

Intuition and meaning of a "discriminating path" in a causal DAG

In Ali, Richardson and Spirtes (2009) (open copy here) and many other papers in the causal DAG literature, there is the notion of a "discriminating path". The definition is: A path $\pi = ⟨...
user avatar
  • 153
3 votes
1 answer
121 views

Weighted adjacency matrix normalization for GCN, how to normalize? what about self-loop values?

I am implementing a GCN that will work on a weighted graph. The edges' weights are in the range [1, 250]. When it comes to normalizing the adjacency matrix for GCNs, the standard formula of a ...
user avatar
  • 308
2 votes
2 answers
118 views

Nodes' attribute scaling/normalization before graph embedding learning - GNN?

In a node classification setting, is it require to normalize/scale graph node attributes before learning node embeddings using graph neural networks? Why?
user avatar
  • 308
1 vote
0 answers
43 views

Marginal Distribution of a Stochastic Block Model?

Let us say I have a Stochastic Block Model i.e. a random vector $X^{(n)} = [x_1,...,x_n]$ where $P(x_i = c) = P_{c}$, where $c \in \{1,...,u\}$, and a random simple undirected graph represented by $Y^{...
user avatar
  • 151
1 vote
1 answer
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
  • 151
3 votes
1 answer
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 ...
user avatar
  • 131
1 vote
0 answers
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 ...
user avatar
1 vote
0 answers
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 ...
user avatar
1 vote
0 answers
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$ ...
user avatar
  • 151
0 votes
0 answers
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 ...
user avatar
0 votes
1 answer
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 ...
user avatar
  • 1
0 votes
0 answers
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 ...
user avatar
1 vote
0 answers
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
  • 11
0 votes
0 answers
11 views

Higher order tensors for describe (hyper) graphs and features attached

I'm trying to understand better some notation I'm reading in the following paper: https://arxiv.org/pdf/1901.09342.pdf In particular, graph or hyper graph data can be described by using tensors $\...
user avatar
0 votes
0 answers
17 views

Is there a concept for "almost parallel" edge?

By "almost parallel" I mean if set S of closing nodes has many conflicting edges with set T of closing nodes, then the edges between them are almost parallel. The emphasized edges in this ...
user avatar
  • 267
2 votes
1 answer
65 views

Trace of quadratic form with Laplacian matrix notation

Reading some papers about spectral graph analysis and graph neural networks I have found the following notation which I'm not too sure how to expand: Given matrices $F, L \in \mathbb{R}^{n \times n}$, ...
user avatar
0 votes
1 answer
83 views

I-map Bayesian Network, Practical Explanation

I am having diffculty understanding the concept of an I-map in the context of Bayesian Networks. According to the PGM textbook by Koller & Friedman, an I-map is essentially a set of conditional ...
user avatar
0 votes
0 answers
11 views

attributed graphs

how can I cluster a node attributed graph? Imagine that nodes contain 3 numeric attributes and edges between nodes are weighted. are there any algorithms in python to cluster this graph based on the ...
user avatar
1 vote
0 answers
31 views

Validation of Clustering with labels

I am currently trying to perform clustering on 8 different datasets where I have 40-100 "labeled" data points per data set, representing which data points belong to the same cluster. I ...
user avatar
  • 111
0 votes
0 answers
40 views

What is the expected average diameter of an Erdös-Renyi graph?

What is the expected average diameter of an Erdös-Renyi graph $G=(n,p)$ with edges $E$ and nodes $V$ where $$avg(G)= \frac{1}{|V|^2} \sum_{v\in V} \sum_{u\in V} len(min_p(u,v))$$ is the average ...
user avatar
0 votes
0 answers
19 views

Which Connected Component algorithm is implemented in GraphX?

I would like to know which connected component is used by GraphX? I have found it on the internet but the only result I got is the tutorial on how to use the code. It will be better if there is a ...
user avatar
  • 113
1 vote
0 answers
27 views

Difference between types of solutions in network matchings? [closed]

So there are so many different types of solutions: pareto, stable, rank-maximal, etc. etc. How do anyone know which one to use for any given problem? Particularly when some of them may not exist? And ...
user avatar
0 votes
0 answers
15 views

Is there a way to predict not directly links(edges), but only a specific attribute on an already existing link?

I have a complete MultiDiGraph, a street network. Some of the attributes of the edges (road segments) of the graph are missing. Is there any way to predict them? I don't want to make a link prediction,...
user avatar
  • 115
2 votes
0 answers
26 views

Summary on Non-Deep-Learning based Graph Machine Learning Algorithms

I have a classification task for predicting some node attributes, and I would like to find some machine learning algorithms that can be applied to graph data, and are not deep-learning or neural ...
user avatar
  • 1,643
1 vote
1 answer
41 views

Conditional Probability for Network Science

My network has 100 nodes and 196 edges. Each node has an attribute of "smoker" or "non-smoker". There are 5 smokers and 95 non-smokers. I want to know the probability of being a ...
user avatar
0 votes
0 answers
10 views

Proof independence using Markov networks

Let $f$ be a probability density function. Also, let $V_1, ..., V_n$ be vertices in the Markov network graph. Prove if $f(V_1| V_2, V_3, ..., V_n) = f(V_1| V_3, ..., V_n)$ then there is no edge ...
user avatar
0 votes
0 answers
17 views

Can someone give me an example of frequent large subgraphs being outlier?

I read it from a lecture note: ...
user avatar
  • 101
2 votes
0 answers
40 views

Intended selection bias

Sampling or selection bias is often presented as something that has to be overcome, avoided, or at least appropriately considered because it's a problem otherwise. I wonder how often situations arise (...
user avatar
0 votes
0 answers
40 views

Re-generate the exact underlying data from an exact MRF model or any other PGMs

I was wondering if there exist a way to re-generate the actual underlying data (not a sample!) from a given exactly learned MRF. In other words, lets say I have a discrete factorised joint ...
user avatar
  • 1
0 votes
0 answers
45 views

Link Prediction on Directed Graph using node embedding

I am trying to solve the link prediction problem in a directed graph using supervised learning. In the case of an undirected graph, it is pretty straightforward. For instance, first, compute the ...
user avatar
2 votes
1 answer
434 views

How to translate eigenvectors and eigenvalues to the number of clusters in spectral clustering?

I have generated this output, where L is the Laplacian Matrix, D is the degree and A is the adjacency matrix: I can see the eigenvalues and eigenvectors are returned. I am unsure how to interpret ...
user avatar
  • 73
3 votes
1 answer
86 views

Build graph of transitive relationships [closed]

I am wondering given the type of directed graph A, how do I convert it into the type of directed graph B? Basically, in graph B, I want to ignore Node X and only retain the Node T. Conceptually, I am ...
user avatar
1 vote
0 answers
25 views

Is it possible to get negative (True Negative)?

I have 3600 samples as my dataset. I split the dataset into the train (2700) and test (900). My problem is related to new link prediction. I am using the Common ...
user avatar
0 votes
0 answers
31 views

Network topology of dropout

So dropout is a popular way to regularize neural networks by randomly removing nodes in the network. There are similar methods that remove edges, as well as skip connections which introduce ...
user avatar
  • 349
1 vote
0 answers
14 views

Estimating future graph size given partial graph size

(This question compares a branching-fiction novel to a disease, bear with me.) This is for fun, my friends and I are writing a branching-fiction novel: A black node is a concluding chapter ("The ...
user avatar
  • 111
2 votes
0 answers
55 views

0-1 laws in random graphs: probability $\beta$ is large if $k$ is large

How has the author derived here on the page 3 in the context of random graphs and 0-1 laws that $\beta$ is large if $$k\geq ((\frac{2}{\alpha})\log n)^{\frac{1}{2}}$$ ? What I did is this: I've ...
user avatar
2 votes
0 answers
84 views

Fast uniform sampling of walks from directed graph

Given a directed graph $G=(V, E)$ my goal is to sample a set of walks $W\subset\mathcal{W}$ where $\mathcal{W}$ is the set of all walks in $G$. I want each walk to be sampled with the uniform ...
user avatar
  • 21
2 votes
0 answers
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 ...
user avatar
  • 444
1 vote
1 answer
25 views

Given a graph, test if some vertices are more connected than the background

I have a neighborhood graph of some 10k vertices (a k-NN graph of single-cell RNA-seq data). I am interested if a given set of vertices is more connected to each other than you would expect by chance. ...
user avatar

1
2 3 4 5
8