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
6 views

Does over-smoothing affect graph classification? [closed]

over-smoothing directly affects node classification, does it affect graph classification ?
1
vote
1answer
15 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
19 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
25 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 ...
0
votes
1answer
38 views

Why dirac kernel is 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
14 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
13 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
57 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
15 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
8 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
8 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
21 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
8 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
8 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)}{\...
1
vote
0answers
15 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
44 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
21 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
30 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
49 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
14 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
14 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
12 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
18 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
12 views

binwidths/no. of bins when overlaying two histograms

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 ...
0
votes
0answers
8 views

Integrate popularity with the approximate nearest neighbor searching?

I studied the mechanism of some ANN algorithms but only find that each stored vector is treated equally. That is, the popularity of the corresponding vectors are ignored. How can all vector ...
0
votes
0answers
18 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
vote
0answers
31 views

HNSW: meaning of “length scale” and “characteristic radius”

I'm reading through the paper behind the well known Hierarchical Navigable Small World (HNSW) graphs for approximate nearest neighbor search, but I don't understand one of the core concepts. The ...
0
votes
1answer
83 views

what is the difference between GCN and random walk

Anyone could explain to me what is the difference between graph convolutional network (GCN) and random walk? or they are the same? Any further explanation will be much appreciated.
2
votes
1answer
25 views

Identifying identical graphs or adjacency matrices of graphs

I was wondering if someone has a good idea for checking whether two graphs are the same (for example, based on an adjacency matrix). Ideally, in a computational efficient manner that can be done on ...
2
votes
2answers
112 views

When to use graph clustering (by constructing a graph from raw data) vs conventional clustering methods?

This is a conceptual question. Say I have some tabular data, and a known similarity function i want to use to compare records in this tabular data. Records correspond to members of a MileageProgram, ...
4
votes
1answer
96 views

A graph-based clustering problem

I have a graph in which each node is associated with a time stamp. I have around 15-20 nodes associated with each time stamp. The edges are not weighted & there cannot be an edge between nodes ...
2
votes
1answer
47 views

Degree and weight preserving randomisation in networks

I have a network in which nodes are highly interconnected (250 nodes where 90% of the nodes have degree = 249). The connections are weighted with a normalised index that goes from 0 to 1, where 1 ...
2
votes
1answer
67 views

What are the common practices to weight tags relations?

I am working on a webapp (fullstack JS) where the user create documents and attach tags to them. They also select a list of tags they are interested in and attach them to their profile. I am not a ...
1
vote
0answers
24 views

What does each graph cuadrant means with LDA vis plot from R? [duplicate]

I am speeking about this graph, that shows a big probability mass. This is the way that it finally shows with some data I found online and used to understand Latent Dirichlet Allocation topic ...
2
votes
0answers
35 views

Intuition behind null model for disparity filter algorithm

I'm trying to better understand the disparity filter algorithm for weighted networks: Original paper: https://www.pnas.org/content/106/16/6483 Wikipedia link: https://en.wikipedia.org/wiki/...
3
votes
1answer
52 views

Community-detection algorithm to use to divide large network (200k nodes) into few (~5) communities

I have a large moderately dense network (50k nodes, 300k edges) and want to divide this into few (5-10) communities, based on how densely connected the nodes are. I've been looking into the ...
0
votes
0answers
40 views

Probability of a graph

Given a graph $G=(v, \varepsilon)$, where $v$ is the set of vertices and $\varepsilon$ is the set of edges of the graph, I would like to write the probability $p(G)$ of $G\in\mathcal{G}$, where $\...
7
votes
1answer
228 views

What would make Graph Neural Networks better than 'normal' Neural Networks?

I am quite new to the area of artificial intelligence and deep learning, so I am exploring some of the available techniques and models. Throughout my readings, I noticed a growing trend towards using ...
1
vote
0answers
47 views

How to compare 2 groups with different sizes?

I wish to compare network density metrics. I have 6 densities from 6 different graphs. Each graph has different number of nodes as well different number of edges. I wanted to compare the 6 ...
0
votes
0answers
13 views

what is the probability that a randomly chosen vertex belong to a small component of size S?

I was reading chapter 12 of "Networks: An Introduction Book by Mark Newman" about Random Graph. part 12.6 of the book is about the small components in Random Graph. page 405 equation 12.24 and 12.25 I ...
1
vote
0answers
35 views

Why do we have to convert Bayes' net to MRF before applying Belief propagation?

is that even correct in the first place? if yes, then why? I've seen articles talking about inference in Bayes' nets, and I've seen others talking about conversion. I don't have the full picture.
1
vote
0answers
9 views

What is constraint and effectivesize in structural holes?

Today, I spent the whole day trying to understand what structural holes in network means. More specifically I want to clarify what the two measurements constraint and effective size means? Is it good ...
3
votes
1answer
26 views

Divide Minimum Spanning Tree into Equal (Disconnected) Chunks

Does anybody know an efficient algorithm for dividing Minimum Spanning Tree (MST) into equal in size disconnected sub-trees? I'm not saying that it is a particularly hard task, but maybe there exist ...
0
votes
0answers
35 views

Cutting dendrogram at certain point

I have a question about cutting dendrogram like that It shows some hierarchy in the prison I have to cut it to separate the group. Is it possible to cut not all dendrograph at the same height like ...
1
vote
1answer
45 views

Why Boltzmann machine is represented as a fully connected graphical model?

The joint factorizes into unaries and pair-wise potentials. If that is the case, then why do we represent it as a fully connected graph? It is misleading and gives the impression that the joint cannot ...
0
votes
1answer
20 views

Describe the graphs linear association between these two variables height and width

I have written the code below to create a scatterplot to visualize whether the two variables are linearly associated but I am not sure how you would describe this output. I would say it is not ...
0
votes
0answers
13 views

correlation between signals

I have some sensor measurements (traffic speed cameras) which are deployed all over a city and totalling about 10000. I have data from them for the last 8 years with a fairly decent temporal frequency ...
0
votes
0answers
11 views

Producing a graph for OSL results

I would like to overlay 5 OSL age estimates, which are essentially just dates e.g. 5ka BP, 7ka BP, 9ka BP, and 11ka BP onto an existing graph that shows temperature change (called bond cycles) during ...
1
vote
0answers
43 views

What is the difference between node clustering and network community detection?

Node clustering algorithms in which we attempt to determine dense regions of the graph based on edge behaviour(either be a distance value or a similarity value). The more similar nodes come together ...

1
2 3 4 5
7