Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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

0
votes
0answers
16 views

Why it is not recommended to index relationships in a graph database [migrated]

In book Neo4j in Action by Aleksa Vukotic and Nicki Watt, the authors says 'In our experience, it is less common for relationship indexes to be good solutions. We are not saying that relationship ...
1
vote
0answers
19 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
31 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
36 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
0answers
15 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
24 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
12 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
17 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 ...
4
votes
2answers
85 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
23 views

What is the purpose of finding the Maximum Spanning Tree?

I'm referring to Chow-Liu algorithm in Bayesian network structure learning. We first construct a Mutual Information Graph, and from that we find the Maximum Spanning Tree. But, once we got the tree, ...
1
vote
0answers
14 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
67 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
16 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 ...
0
votes
0answers
19 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
1answer
19 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
40 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
10 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
9 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
14 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 ...
0
votes
0answers
39 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
24 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
44 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
16 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
18 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
21 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
16 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
16 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
18 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
1answer
39 views

Range of eigencentrality scores

I could not find the answer to this question online. In a graph, what is the range of possible values of eigenvector centrality scores? EDIT: Here is an example: ...
1
vote
0answers
37 views

how to make sure the dependent and independent variables measure the same thing?

I am trying to build a model that measures the importance of musicians social network on their number of gigs. I use graph theory and construct the social network based on the line-up of events for ...
0
votes
0answers
15 views

How to interpret networks with multiple states (e.g. timeseries, conditions, etc.) that have same node set?

Apologies if this is too general but I have been thinking about it all weekend and wasn't sure how to move forward with the idea. Here are the types of networks I am dealing with below: I have 2 ...
0
votes
1answer
76 views

Densest subgraph : density of an intersection

I found an exercice in my textbook and I can't find the answer : $G = (V;E)$ an undirected graph. $H_1 = (V_1;E_1)$ and $H_2 = (V_2;E_2)$ are two densest subgraphs in G, i.e., for any subgraph $H = (...
1
vote
0answers
79 views

Bayesian Networks - Factor Graphs - Belief Propagation - Numerical stability

I am trying to do inference for a Bayesian Network with discrete probabilities. I converted the network to a factor graph and implemented the sum-product algorithm (belief propagation). My goal is ...
0
votes
0answers
102 views

How can I generate random DAG's in a good way?

I am trying to generate random DAG's (Directed Acyclic Graphs)... However, the result is not very satisfying to me; What I am doing: I generate a random graph with the Erdős–Rényi model; More ...
1
vote
0answers
18 views

Conceptual question: A confidence interval around the mean for t-values

I have a weighted graph of an airport network, where each node is an airport (associated with an N, or the number of flights landing at or leaving the airport). The ...
1
vote
1answer
8 views

Manber's graph-partitioning algorithm implementation

I'm having trouble understanding a part of Manber's graph-partitioning algorithm, presented in A Text Compression Scheme that Allows Fast Searching Directly in the Compressed File. Generally speaking ...
0
votes
0answers
22 views

Finding most valuable paths

I am trying to analyze a data set of user journeys. My data looks as follows ...
0
votes
0answers
11 views

Computing power for linked (i.e., graphs) vs. non-linked data

Why processing linked data (i.e., graphs) require much higher computing power than processing non-linked data?
1
vote
0answers
68 views

How to calculate associated degree of freedom of linked nodes in graph

I am working on text analytics and building a knowledge graph with high frequency entities (noun chunks) as graph nodes and their linkage between co-occurrence in a sentence as edges. I am able to ...
2
votes
3answers
88 views

How to find strongly connected subgraphs in a graph? [duplicate]

I have a simple, undirected graph where I'd like to detect "natural" subgraphs where vertices are connected intensively internally but sparsely externally. The problem is that I have no exact hint ...
0
votes
0answers
33 views

How to build a conversational graph knowledge?

I could not find a solution for my problem, browser points to chatbots. I have 5 or more people sitting around the table. I want to build a knowledge graph from their conversation. Where can I read ...
1
vote
1answer
165 views

Centrality of a directed network with edge weights - Gephi

I have the following network of court judgments in the form of a big network.(50k+ nodes and 100k+ edges with weight values). The size is the number of citations. The idea is that court judgments work ...
1
vote
0answers
49 views

Similarities / suggestions of multi-attribute entities

Dataset: I have 200 000 entites, these have zero or more of 1000 attributes (commonly 1-20 of them) The attibute relation is weighted 1-3 Its stored in a relational database modeles as Entity, ...
1
vote
1answer
312 views

Assortativity coefficient in igraph

In the context of Social Network Analysis, I want to compute the homogeneity of different networks for specific attributes. For this case the igraph package contains the method assortativity() to ...
2
votes
1answer
185 views

Computation of Network Homophily / Heterogeneity

I am quite confused about the calculation of network homophily in network analysis. Right now I am computing the homophily using the following function, which has been written and also described by ...
0
votes
0answers
22 views

Investigating the change of a network / factorial structure over time

I have several variables (questions from a questionnaire) that regroup into several factors (using factor analysis). However, I would be interested in knowing how this factorial structure changes ...
1
vote
0answers
18 views

How to get accurate shortest paths for signed weighted graphs with negative cycles?

I work with resting state functional data and my lab supervisor prefers to use signed, weighted, partial correlation networks (it's fairly standard in rsfc analyses). An unfortunate characteristic of ...