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
0answers
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 ...
0
votes
0answers
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 ...
1
vote
0answers
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 ...
0
votes
0answers
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, ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
1
vote
0answers
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 ...
0
votes
0answers
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,...
1
vote
0answers
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
0
votes
0answers
15 views
1
vote
0answers
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 (...
0
votes
0answers
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....
0
votes
0answers
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 ...
0
votes
0answers
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 ...
2
votes
1answer
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 ...
3
votes
1answer
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
1
vote
0answers
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 ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
1
vote
1answer
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. ...
0
votes
0answers
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 ...
0
votes
0answers
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})$ ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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 ...
2
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
1
vote
0answers
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 ...
0
votes
0answers
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$...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
2
votes
1answer
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 ...
2
votes
3answers
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 ...
1
vote
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
111 views

Congestion of N-input Butterfly network

What is the max congestion of an N-input butterfly network where N is an even power of 2? I'm pretty sure it is the square root of N, but what is the exact proof for that?
0
votes
0answers
38 views

Comparing Directed Unweighted Graphs with a Dissimilar Number of Nodes

I'm looking to compare 2 unweighted directed graphs and get an (ideally differentiable) similarity score. Both graphs describe a trajectory in a 2d space. The reference graph is a step by step guide ...

1
2 3 4 5
7