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
2
votes
1answer
41 views

Build graph of transitive relationships in R [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 ...
0
votes
0answers
27 views

What is the best way of assigning edges in Graph Neural Networks?

The most common method of assign edges is if two nodes are within a fixed Euclidean Distance of each other. But I've not seen any other techniques, I was wondering if there are any better methods out ...
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
24 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
18 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
10 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
11 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
47 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
77 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 ...
1
vote
0answers
23 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
23 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
10 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
12 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
17 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
30 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 ...
0
votes
1answer
17 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
35 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
51 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
18 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
0answers
33 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
64 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
22 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
15 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
45 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
48 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
27 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
30 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 ...
1
vote
2answers
92 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
129 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
16 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
107 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
23 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
vote
0answers
10 views

Accounting for connectedness during the analysis of nodes in a directed acyclcic graph

I am studying a river network and environmental features measured at different stations along the network. Often, one station is higher up the river than another (or multiple others). I can ...
0
votes
0answers
9 views

Measuring the effect of initial node positions to clustering

I am trying to measure the effectiveness of using clustering algorithms to generate clusters within Graphs. The intention is for nodes which have high edge weights amongst each other to be clustered ...
0
votes
0answers
39 views

Hierarchical graph clustering using a kernel matrix in R

I have a set of 9 directed graphs of differing sizes and I'd like to use graph clustering to create a dendrogram illustrating their structural similarity, similar to what's done in the NetConfer ...
0
votes
0answers
9 views

degree centrality for two clusters in the network to identify most central influencers “unique” to each cluster

I have a network containing 2 groups of people A and B (taken from twitter). I want to find the most influential people within each group but I want to make sure that these people are specific to ...
0
votes
0answers
9 views

Grouping nodes together that have no connection

We have a data set of 200 people and how much they have interacted with each other based on email metadata (collaboration hours = edge weight). We were asked to put people into 20 groups of 10 so that ...
0
votes
0answers
20 views

definition of weights in UMAP algorithm

In the UMAP algorithm on p. 13 they define the weight between a point $x_i$ and it's j-th nearest neighbour $j \leq k$ as $$w((x_i, x_{ij})) = \exp\left\{\frac{- \max(0, d(x_i, x_{ij})- \rho_i)}{\...
3
votes
1answer
30 views

Clustering Coefficient of Erdos Renyi Model

The clustering coefficient for erdos renyi model $G(n,p) = p$. Now i have been studying in various papers that it cannot model real world networks which has high clustering coefficient. My question ...
1
vote
1answer
66 views

Interpretation of pooling in Graph Neural Networks

The paper Hierarchical Graph Pooling with Structure Learning (2019) introduces a distance measure between: a graph's node-representation matrix $\text{H}$, and an approximation of this constructed ...
0
votes
0answers
23 views

How to compare 2 measurements of homophily in

Given a Bi-directional graph G(V,E) with node labels corresponding to either Red or Blue, where (Ai ->Bj) denotes a directed edge from some vertex A to another vertex B in G(V) with i,j being one of ...
1
vote
0answers
40 views

Are there any statistical methods to test the difference in network modularity?

Currently, I'm working on network analysis on multiple graphs. One of the analyses I've done is calculating modularity scores based on the louvain clustering method. In doing so, are there any ...
1
vote
0answers
84 views

Interpretation of the reachability plot (optics clustering))

https://scikit-learn.org/stable/modules/clustering.html#optics Does anyone know to read the reachability plot produced in optics clustering? What indicators exist that allow the user to evaluate the ...
0
votes
0answers
15 views

Graphs to sequences

I would like to apply network metrics to sequence analysis. The approach is described in this paper https://link.springer.com/chapter/10.1007/978-3-319-95420-2_7 However I don't know how to translate ...
0
votes
0answers
18 views

embedding a graph in n dimensional vector space and feed into a machine learning model

So I want to do some graph classification and regression. That is right! the training set are graphs. So my question is how can we embed a graph into a n dimensional vector space? Suppose the graph I'...
1
vote
0answers
15 views

Downsampling majority class of binary labelled graph

I have a graph of user-to-user interactions, where the vertices (users) are given a binary label. I want to generate a downsample of the majority class (and keep all of the vertices in the minority ...
2
votes
0answers
23 views

Is a grid-like network more efficient than a random network?

Imagine two different types of street networks with the same number of nodes and where edges are weighted according to their length. Both network types cover the same geographic area (say 1km²) and ...
0
votes
0answers
20 views

Binwidths/no. of bins for 2 histograms for overlaying them

Should the binwidths for two histograms be same or no. of bins in both histograms be same when they are overlayed for comparison? or there is no correlation? I am comparing histogram of centrality for ...

1
2 3 4 5
7