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

4
votes
2answers
70 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
21 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
13 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
53 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
13 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
17 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
18 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
33 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
11 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
9 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
31 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
22 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
40 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
12 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
20 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
25 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
15 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
15 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
38 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
32 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
66 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
64 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
39 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
82 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
16 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
128 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
38 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, ...
0
votes
1answer
234 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 ...
1
vote
1answer
139 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
16 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 ...
4
votes
0answers
87 views

How to estimate passengers destinations from flightradar data?

We have a graph with vertices corresponding to airports and edges corresponding to flights between those airports. On edge between airports A and B we have and number of passengers transferred from A ...
2
votes
0answers
32 views

How to measure “cyclicity” of a directed weighted graph?

Say you have a weighted directed graph with (potentially) some cycles in it. You want to have some sort of a measure of how "cyclical" this graph is. The requirements are: This measure C=0 on an ...
0
votes
0answers
85 views

agglomerative clustering of undirected weighted graph

Let's say I have a simple graph of undirected, weighted edges. I want to agglomerate nodes one-at-a-time by combining the two nodes which have the highest weighted edge, recalculating remaining edge ...
0
votes
1answer
22 views

How to Cluster Hierarchical Network Data

I have thousands of "small" networks that are strictly hierarchical in nature. Here is an example (some are much deeper, much wider etc) but this is the strict structure: How can one cluster (e.g. k-...
4
votes
2answers
72 views

How to uniformly sample vertices from a large graph with given distance from a fixed vertex?

Given an undirected graph $G=(V,E)$ and some vertex $v_0\in V$, let $V_k=\{\,v\mid v\in V,d(v_0,v)=k\,\}$ be the set of all vertices with distance $k$ to $v_0$. How can I quickly draw uniform samples ...
0
votes
0answers
84 views

Graph-Based Semi-Supervised Learning for NLP Text Classification

I have hundreds of various job titles, where some of the titles may sound different but ultimately should be classified to be the same position (ex. Call Center, Call Center, Customer Contact Center ...
1
vote
0answers
75 views

What is the most efficient implementation of the min-k-cut algorithm?

Simple question, I'd like to apply min-k-cut algorithm on a graph to partition the graph in k clusters by minimizing the sum of edges cut during the formation of clusters. In my case I already know k ...
1
vote
1answer
38 views

Clustering: Clique vs. Agglomerative with Complete-Link

In my data, I have a defined a symmetrical relation $R$ where $R(i,j)=R(j,i)$ indicates that $i$ and $j$ are closed each other. I need to find cliques $C_1,C_2,\dots,C_n$ where $C_k\cap C_l=\...