# 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'.

300 questions
Filter by
Sorted by
Tagged with
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 ...
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, ...
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.
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
14 views

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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/...
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 ...
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 ...
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 ...
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 ...
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 ...