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

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

Can you normalize graph density [closed]

I wish to normalize network density metrics [0 - 1] and fit into a bar plot. I have done a simple normalization method - MinMax. The main reason behind this is the sample group size: 4, 24, 52, 77, ...
0
votes
0answers
12 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.
0
votes
0answers
5 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
24 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
15 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
27 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
17 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
9 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
26 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
32 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
23 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
14 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
11 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
23 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
13 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
36 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
11 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
26 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
33 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
45 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
149 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
46 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 ...
0
votes
1answer
97 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 ...
3
votes
0answers
15 views

Spectral graph convolutional network, re-assigning indices

This is a silly question for whom is familiar with the theory. I came across few papers that use a particular definition of convolution, designed to work with graphs, for example see section 2.1. of ...
0
votes
0answers
37 views

Understanding Assortativity in Networks

I'm not the best at math or graph theory and I'm trying to understand the formula for assortativity here $$r=\frac{\sum_i e_{ii}-\sum_i a_i b_i}{1-\sum_i a_i b_i}$$ where $e(i,j)$ is the fraction of ...
5
votes
2answers
117 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
vote
0answers
15 views

Graph clustering for balanced sum of absolute deviations within each cluster (same sum of intracluster distances)

I'm given a set of points and a distance matrix. With these I'm trying to develop an algorithm similar to k-means that tries to minimize the sum of distances from each cluster datapoint to it's center ...
4
votes
1answer
111 views

Front-door criteria - what does the second requirement mean?

I'm reading Causal Inference in Statistics: A Primer by Pearl, et. al. and I'm a little confused by the definition of front door. The definition in the book (Definition 3.4.1) is: A set of ...
0
votes
0answers
19 views

igraph - Minimum vertex set origin for destination

Part igraph question, part graph theory question. I have a digraph from a set of origin vertices (warehouses) to destination vertices (customers). A given origin vertex has edges only to a limited ...
1
vote
1answer
58 views

Graph Theory - Network Homophily with continuous node attribute

I have a setup where I have a directed graph $G = (V,E)$ and a node attributes vector $\overrightarrow{x}$ with $|\overrightarrow{x}| = |V|$ and $\forall x_i \in \overrightarrow{x}$, it holds $x_i \in ...
1
vote
2answers
26 views

representative nodes in modular network

I want to find the most representative nodes in each module in a modular network. I have used the Louvain algorithm on my graph and found two main modules. Now I want to know what nodes are the most ...
0
votes
1answer
50 views

In directed acyclic graphs, is there a dependency in opposite directions?

Suppose we have this graph: (a) ==> (b) ==> (c) Does this mean that P(a|b)=P(a) because the arrows indicate that b is dependent on a and not the other way? If not, then why do we use arrows?
0
votes
0answers
16 views

Why is a single element getting better results than the sum?

I need an intuition how this is possible - Imagine I have a DAG(directed acyclic graph), so a graph without cycles and only directed edges; Now for every DAG with $d$ nodes there is (at least) one ...
0
votes
0answers
16 views

Clarification on notation used to present back propagation algorithm in 'The Deep Learning Book'

In the deep learning book (free version is available online) the backpropation algorithm is explained in section 6.5. I have a question on equation (6.53): $$\frac{\partial u^{(n)}}{\partial u^{(j)}}...
0
votes
0answers
10 views

Graph problem with X nodes looking for Y paths with the most similar length. (shortest path / Chinese post man problem)

There is exactly 1 start node and 1 end node. There are also X (in this case 7) nodes, each connected to all other nodes and the start and end node with different lengths of the paths. The visitor ...
1
vote
0answers
12 views

Largest connected group of identically distributed nodes in d.r.v sample graph

I have come across an unfamiliar and somewhat interesting problem while attempting to write an algorithm for an image processing application and was wondering if any of you had any ideas that might be ...
0
votes
0answers
25 views

Nomenclature of hierarchical clustering constellation plot/graph

What is the name for the process/method by which I select the branch that has that dot, circled in red, from within the hierarchical clustered model? This is a constellation plot, made in JMP: I am ...
1
vote
0answers
276 views

What is the difference between homogeneous Markov chains and unhomogeneous Markov chains?

I learned that a Markov chain is a graph that describes how the state changes over time, and a homogeneous Markov chain is such a graph that its system dynamic doesn't change. Here the system dynamic ...
0
votes
1answer
36 views

Graph analysis : extract highly connected nodes in a weighted 2-group directed graph

I've a question regarding the extraction of highly connected nodes. My graph is directed graph with only two groups of nodes (X and Y). In the example below group X (node 0, 1, 2 and 3) points to ...
0
votes
1answer
64 views

Which regression used for normalized count data

I am working with social network data. I have multiple networks of various sizes and I'm calculating indegree (the number of connections between people) in each of the networks. I've been told to ...
0
votes
0answers
28 views

How to approach node/graph classification in an event?

I'm facing a new project and thought about maybe going in the direction of Graph-Neural-Networks. My data comes in the form of events (unrelated to each other), the data in each events contains a 2D/...
2
votes
0answers
24 views

Adjacency matrix of amino-acid residue [closed]

How to get the mathematical representation of the chemical bonds in protein residue or the whole protein? Is it possible to get the connectivity matrix or a pairwise description? The example in the ...
0
votes
1answer
23 views

Dividing datasets into fully-correlating subsets

I have a dataset of $N$ variables of which I know that (at least) one combination of their disjoint subsets results in non-negative correlation coefficients for all variables in these subsets. The ...
0
votes
0answers
27 views

Why does a minimum value cutoff in edge values create this shape in the log-log plot of the edge values aggregated to start nodes?

I have a weighted network dataset that looks like this: The prev and curr values contain webpages, and n is the number of times users went from the prev webpage to curr webpage. So, each data row is ...
0
votes
0answers
21 views

If I(G) = I(G') do they have the same skeleton and the same v-strucures except those in complete (sub-) graph?

I thought if two different graphs G, G' have the same skeleton and the same v-structure, then I(G)=I(G′) and I(G)≠∅. But does the converse also holds? In this case a complete graph doesn't apply ...
0
votes
0answers
17 views

Combining centrality into one based on same data type

I'm working on a project that involves count data (specifically number of interactions) from multiple different districts in a specific area. Our team has been talking about calculating a few ...
0
votes
1answer
21 views

Determining the closeness of nodes by their neighbours

Background I have a directional network that is comprised of two types of nodes, business_sector nodes, and event_type nodes. ...
2
votes
2answers
61 views

Order of Conditional Independence Tests

I'm studying the PC algorithm for learning the structure of a Bayesian Network. One of the steps refers to performing several rounds of conditional independence tests of increasing order, zero, first,...