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

350 questions
Filter by
Sorted by
Tagged with
8 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 ...
10 views

### Updating map by location history of users [closed]

I am running a map service (similar to Google Maps). Suppose that I draw a path from A to B. It is in fact a list of (lat,long). I have the location history (GPS-based) of users when they move from A ...
24 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 ...
13 views

### Can we consider new predicted links (those have score 0) after applying some link prediction algorithms?

We can use different link prediction algorithms to predict new links. Say for example, Jaccard index, Resource Allocation, ...
12 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 ...
18 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 ...
26 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 ...
14 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,...
18 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 ...
31 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 ...
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 ...
15 views

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

I read it from a lecture note: ...
35 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 (...
15 views

### Maximum number of leaves in top-down binary decision tree (CART/C4.5)

Out of curiosity, I was wondering if there are any theoretical bounds/guarantees on the number of leaves that a classification decision tree built using an impurity-based algorithm (such as CART or C4....
36 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 ...
21 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 ...
149 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 ...
82 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 ...
11 views

### Setting up an optimization problem using image datasets

I've been working with computer vision for a few months now. I've read a lot of papers that introduce novel models that do well on imagenet. I recently started reading a larger variety of CV papers ...
24 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 ...
29 views

### How do I calculate the accuracy for graph mining in terms of (top 1%)?

I have some confusion regarding calculating the accuracy of a graph mining (link prediction)0 project. I have 3600 samples as my dataset. I split the dataset into the train (2700) and test (900). My ...
26 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 ...
12 views

### Map between variables, using cross-correlation

I have a cross-correlation matrix, $C_{nm}$, between two sets of variables, and I would like to establish the correspondence between the row and the column variables. My current approach is to convert ...
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 ...
51 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 ...
79 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 ...
27 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 ...
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. ...
20 views

### Fixed number of communities using community detection algorithms in r

I have a graph G with 10000 nodes and 30000 edges. I want to partition the graph into two communities only (i.e., Community A and Community B). Criteria: First, we have to make a subgraph of 1000 ...
16 views

### Statistical analysis of website logs

Setup and data My setup is as follows: I have a graph-like structure $G=(V,E)$ which emanates from website logs: a log $\ell$ is simply a sequence of vertices $\ell = (v_{i_1},v_{i_2},\dots, v_{i_L})$ ...
20 views

### Network-wide closeness centrality in weighted undirected graph (closeness centralization)

I am using the Igraph package in R to analyze a series of different networks and I wanted to compare them. Specifically, I wanted to compare their closeness centrality. This is an undirected weighted ...
22 views

### What kind of graph shows the distance between any 2 points as a measure of similarity between them?

I would like to start by saying that I have looked across several sites on the StackExchange website, and have determined this would be the best to ask my question as it regards data-visualisation ...
32 views

### Weighted and Probability Graph

I have a simple markov chain with A, B and C states. For each state I have a probability and beyond that, a value. So, for each state transition I have two informations: the probability of the ...
35 views

### Factor graph equivalent to markov networks

Consider the following potential on three nodes. represented by the following factor graph. Now the notes claim that we can represent this factor graph as both a Bayesian network and a Markov ...
177 views

### Why does fast graph convolution need Chebyshev polynomials?

I'm reading the paper Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering and find it difficult to understand the motivation for using Chebyshev polynomials. With localized ...
53 views

### Recognize distribution on integers (>=0) - mean 5, median 2, percentiles 75% = 5, 90% = 13, 95 % = 21, std around 11, power law slope around -2.55

I wonder may be some one seen some family of distributions on integers (non-negative) which may include the distribution with the following properties: mean 5, median 2, std around 11, power law ...
25 views

### How to estimate the probability on an edge appearing in the minimum spanning tree of a graph?

I've been running into this problem recently and I've been stuck on it for a while. I have a set of vertices 𝐺 that form a complete graph. From this I need to sample 𝑘 vertices (which would also ...
101 views

### What is the difference between brokerage and betweenness?

This link describes betweenness: "Betweenness centrality measures the extent to which a vertex lies on paths between other vertices." This link describes brokerage: "Brokerage is a ...
94 views

### Clustering coefficient (equation) for a regular ring lattice

Hi, I would like to understand why the clustering coefficient for a regular ring lattice has the following equation: $C(v) = \frac{3(d-2)}{4(d-1)}$. Do you know how to derive it? Or where I can find a ...
95 views

### R: K Means Clustering vs Community Detection Algorithms (Weighted Correlation Network) Have I overcomplicated this question

I have data that looks like this: https://imgur.com/a/1hOsFpF The first dataset is a standard format dataset which contains a list of people and their financial properties. The second dataset contains ...
16 views

### Graph question - How to compute scaling parameter α after gaining a degree sequence of a graph?

I am a junior data scientist and very new to the graph theory, so I guess my question is stupid. Recently, I have been reading several papers related to a graph theory to try to answer a question that ...
55 views

### How to use belief propagation sum product algorithm in a factor graph to solve inference problem?

I've read about belief propagation and sum product algorithm but still don't know how to apply it. For simplicity, I want to apply it to estimate the variable $x$ from this equation, $y=x+n$, where $n$...
199 views

### Graph convolution network for variable number of nodes

Is it possible to train a graph convolutional network on graphs with a varying number of nodes? I have a dataset of graphs with a range of 400-1000 nodes, though I could see a higher number of nodes ...
38 views

### Similarity between graphs of different sizes

I have two graphs G and G' (of different sizes) and I want to check how similar they are. I have read that the Wasserstein distance is used in this case. How can I use it? In scipy there is the ...
43 views

### Predicting Graph Edge Connections

I have a set of nodes in 3d physical space. Some of those nodes are connected to one another by a graph edge, while others are not. Just because two nodes are physically close doesn't necessarily mean ...
160 views

### Why is Dirac kernel positive semi-definite?

I read a paper Weisfeiler-Lehman Graph Kernel. In this paper, it says: Let the base kernel $k$ be a function counting pairs of matching node labels in two graphs: \$k\left(G, G^{\prime}\right)=\sum_{v ...
213 views

### Document AI : Using FUNSD dataset to train a GNN to classify 'Linked' entities

I have been using the FUNSD dataset to predict sequence labeling in unstructured documents per this paper: LayoutLM: Pre-training of Text and Layout for Document Image Understanding . The data after ...
17 views

### Using a poset or directed graph as input for a neural network

I'm not sure if this is the right community to post this in but I would appreciate any help. As the title states, I'm trying to train a neural network using some unconventional input. I'm wondering if ...