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
4 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
14 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
29 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
13 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
24 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
12 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
9 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
25 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
13 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
43 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
26 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
25 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
27 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
76 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
82 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
87 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
18 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
9 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
32 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
16 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)}{\...
2
votes
1answer
24 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
55 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
22 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
34 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
67 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
15 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
20 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
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
vote
0answers
43 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
125 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
26 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 ...
3
votes
2answers
115 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
98 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
57 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
68 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
25 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
49 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
56 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
42 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
307 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
2 3 4 5
7