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
1
vote
0answers
9 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
28 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
19 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
21 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
18 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
13 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
13 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
9 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
10 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
16 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
21 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
33 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
23 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
106 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
93 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
36 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
64 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
15 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
26 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
35 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
39 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 $\...
6
votes
1answer
137 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
40 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 ...
0
votes
0answers
26 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
7 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
25 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
26 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
35 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
18 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
12 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
37 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 ...
2
votes
1answer
59 views

Network analysis: Formal definition of the number of 1st order neighbours of degree 1

I am looking for a formal definition of a network metric I am using in a scientific article. Let $i$ be a vertex in a graph $G$ and $N(i)$ are the first order neighbors of vertex $i$. I am interested ...
1
vote
0answers
52 views

How can I visualize and cluster weighted graphs in python?

On any ecommerce website, you have options to apply filters to filter out products. For example: So I have data of how many users applied what filters tuples on the website. Which is fetched from ...
0
votes
0answers
16 views

Factorization of a completely connected undirected graph with pairwise compatibility functions

Given a completely connected undirected graph (V,E) such that $V=(x_1,\dots,x_5)$ and $E = ((x_i,x_j)_{i<j})$ for $i,j =1,\dots,5$, it is known that there exists a factorization $$ P(x_1,\dots,x_5) ...
0
votes
0answers
16 views

Null model of a random network formula derivation

This paper generates backbones in a network using a null model. The paper mentions https://arxiv.org/pdf/0904.2389.pdf "The null model that we use to define anomalous fluctuations provides the ...
1
vote
1answer
31 views

The implementation of variable-to-factor and factor-to-variable messages?

I read this tutorial on the implementation of CRF and got to know that the normalization is the sum-product message passing. And I also know that there are two types of messages on factor graph: ...
0
votes
0answers
34 views

How to extract fixed sized feature vector from arbitrary graph data?

So I am dealing with graph data and graph neural networks. Usually a graph convolution network takes an adjacency matrix and one feature vector like this : ...
0
votes
0answers
65 views

node2vec: Intuition behind BFS resulting in embeddings that capture structural equivalence

In the node2vec paper1 it is mentioned that when using BFS to embed nodes, the results correspond to structural equivalence (i.e. nodes that are "bridge nodes" would get embedded close together) ...
0
votes
0answers
13 views

Multiple agents converging at one node, least distance. Name?

So what I have is a graph with multiple agents that begin on a random node. Each edge symbolizes a distance between adjacent nodes. The end goal is to have all the agents meet at the same node which ...
1
vote
0answers
33 views

Summary statistics for bipartite networks

I have a large bipartite network that I would like to summarise. So far, I have found the following summary statistics: Degree centrality Graph density Modularity Nestedness I have not found a ...
2
votes
0answers
34 views

Reference request: Network/graph topology inference

I am a mathematician looking for a survey/book on methods for inference of graph/network topology (structure). Specifically, the kind of problem I am looking to study is as follows: Given a graph $...
0
votes
1answer
93 views

Network analysis - Correlation is positive and significant, but coefficient of simple logistic regression is not significant?

I have an adjacency matrix and another which represents whether the two nodes share an attribute. Consider it like an homophily test. We want to test if the likelihood to form a connect depends on the ...
1
vote
1answer
345 views

Difference between Euclidean ,Pearson, Geodesic and Mahalanobis distance metrics

Given a set of samples $X$. We are tasked to find an appropriate distance metric for $X$ from the given options which are Euclidean Pearson Geodesic and Mahalanobis distance metrics. To solve this, ...
0
votes
1answer
61 views

Implementing a graph convolutional layer, pixel2mesh example

I'm trying to read through some python code in order to understand how to implement a Graph Convolutional Layer. I was particularly interested in pixel2mesh, digging through the code I've found the ...
1
vote
1answer
231 views

What is a factor in the context of Bayesian networks and inference?

I have come across the term "factor" in the context of Bayesian networks and inference (which I am not very familiar with). I've also heard of the expression "factor graph", which is an undirected ...
6
votes
2answers
137 views

Why does Judea Pearl call his causal graphs Markovian?

In his texts on causality, Judea Pearl always refers to the simplest graphs he uses, i.e. the acyclic graphs with independent confounders, as Markovian. I don't see why these graphs contain anything ...

1
2 3 4 5
7