Questions about handling graphs in Mathematica, graph theory, graph visualization, GraphPlot, the built-in Graph type and the Combinatorica` package.

learn more… | top users | synonyms (2)

6
votes
0answers
91 views

HighlightGraph and Hyperlink

In the documentation of Mathematica it is mentioned that you can use Hyperlink and Tooltip as wrapper in a similar manner as ...
6
votes
0answers
122 views

Is there a function to generate a minimal clique cover?

This is a graph problem known as the "Clique Edge Cover" or "Intersection Number" problem, and the goal is to find, from a given graph like $E=\{\{a,b\},\{a,c\},\{b,c\},\{b,d\},\{c,d\}\}$ and ...
5
votes
0answers
37 views

What system functions use VertexWeights?

EdgeWeights -> are used by a lot of functions, but I can't find any exposed usage for VertexWeights ->. I'm not asking ...
5
votes
0answers
61 views

Graph: PropertyValue changes and Dynamic

I almost never work with Graph in Mathematica but lately I helped someone with it. For this, I tried to make an animation using ...
5
votes
0answers
128 views

How to draw block diagrams as Graph objects?

In the documentation ClosedLoopResponsesWithAPIDController, There is a very nice block diagram. I want to create my own block diagrams similar to this. I clicked on the diagram and pressed ...
5
votes
0answers
143 views

Citation of the algorithms used in FindGraphCommunities

For my research work I need to put a comparison of different community detection algorithms. Instead of implementing all those algorithms once again, I would like to use the methods already provided ...
4
votes
0answers
55 views

Finding the minimum vertex cut of a graph

It seems that Mathematica is not correctly finding the smallest set of vertices that will disconnect a graph. Here is an example: ...
4
votes
0answers
170 views

How to draw hypercube graphs

I'd like to draw hypercube projections like those on the Wikipedia page: I tried with HypercubeGraph[6] but the graph does not look right; it is not ...
4
votes
0answers
119 views

Efficient Generation of Subgraphs (or, unfriend a friend a day)

NB: If you're not interested in the back-story, you could simply jump forward to the code which I'm seeking to optimize. Also, I believe this code would only work for MMA 8.0 and above. My friends ...
4
votes
0answers
288 views

Counting paths of a certain length between a source and sink vertex

I have a graph $G$, which may be directed or not, and I was wondering if there was an efficient way of using, say, BreadthFirstScan[] and FindShortestPath[] to count the number of paths between some ...
4
votes
0answers
434 views

Finding a Graph Shortest Path with Custom Graph Distance Function

What is the best way to find a shortest path by using a custom distance function? I'm trying to play a little bit with the concept of using distributions instead of a deterministic weight value for ...
3
votes
0answers
40 views

FindGraphCommunities method options?

FindGraphCommunitites has a couple of method options: "Modularity", "Hierarchical", ...
3
votes
0answers
138 views

Undirected Network and its Monte Carlo Simulation

So I have this array of points, in the form {x, {y,z}}, where x is the node number assigned when I used the locator pane to make a network, and y and z are its unitary coordinates. The graph is made ...
3
votes
0answers
45 views

Does anyone know the options for “HierarchicalEdgeBundling” in Mathematica?

I'm looking to reproduce the types of graph layout that are possible in D3 (http://bl.ocks.org/mbostock/7607999) in Mathematica. Since Mathematica doesn't explicitly support force directed edge ...
3
votes
0answers
171 views

Understanding performance: graph connected components

I need to analyze directed graphs with 10M edges, 1M vertices, and 300K strongly connected components, so that the largest one contains 400K vertices. I read some explanations of Leonid Shifrin here, ...
3
votes
0answers
108 views

Using Graph to cull correlated lists

I have a set of lists that represent molecular descriptors. I need to identify which descriptors are highly correlated and eliminate the correlated pairs. I can represent the connectivity by ...
3
votes
0answers
268 views

A* algorithm for finding shortest path in a graph

FindShortestPath finds the shortest path between two vertices in an edge-weighted graph, allowing a choice between the Dijkstra and Bellman-Ford algorithms. In my (limited) understanding, both of ...
3
votes
0answers
238 views

How to compute the Lovász number for the given graph in Mathematica?

Here is a graph whose adjacency matrix is ...
2
votes
0answers
56 views

Choosing a List as VertexWeight for a TreeGraph

I would like to map every vertex of my TreeGraph to an List. ...
2
votes
0answers
49 views

Belief Network, Bayesian network

There is already a question about simulating Bayesian networks with Mathematica (Mathematica Package for Bayesian Networks). However, are there any packages or approaches which help in computing the ...
2
votes
0answers
52 views

Finding quasi-cliques

Is it possible to find quasi-cliques in a graph in Mathematica 10? I don't think it has been implemented, so are there any solutions to do this? Or do I have to export the graph data somehow and do ...
2
votes
0answers
54 views

Can BreadthFirstScan be modified?

I would like to obtain a "slick" implementation of A*-search algorithm on Graph objects, using the built-in BreadthFirstScan (if that is possible at all). I noticed that BreadthFirstScan is static in ...
2
votes
0answers
289 views

Why my Mathematica 9.0.1 wont work with some samples of Mathematica in Graph Theory?

I updated my Mathematica recently to 9.0.1 cause the previous version was giving me freaky result especially in FindMinimumCostFlow and ...
2
votes
0answers
169 views

Fast calculation of commute distances on large graphs (i.e. fast computation of the pseudo-inverse of a large Laplacian / Kirchhoff matrix)

I have a large, locally connected and undirected graph $G$ with $\approx 10^4$ vertices and $\approx 10^5$ to $\approx 10^6$ edges. Moreover I can bound the maximum vertex degree as $Q_{max}$. I ...
2
votes
0answers
110 views

Strange double evaluation using MorphologicalGraph

(MMA 9.0.0 on Mac OS/X 10.8) Please consider the following snippet (this is as SMALL as I could make it -- my attempts at making a smaller repro-case eliminated the effect that I am investigating) ...
2
votes
0answers
213 views

How can I compute the chromatic index and number of a graph?

I saw a recent question from M.R. and realized there is no function to compute the chromatic index and number of a graph, other than a really slow method in the now deprecated Combinatorica. So, how ...
2
votes
0answers
208 views

How to predict some constant number of values with NeuralNetworks

Example: << NeuralNetworks` data = {Sin[#]} & /@ Range[0, 4 Pi, 0.5]; learn = data[[1 ;; 15]]; Now, lets fit our neural network: ...
1
vote
0answers
74 views

Is there a minor bug in Neal Alexander's TopologicalSortAll[]?

There is an amazing answer to this question: All possible topological orderings of a graph By Neal Alexander. However, as user "dark blue" (I am not this user) notes: ...
1
vote
0answers
39 views

Finding optimal inclusion cutoff to define subgraph of a “large” weighted graph

I have a weighted graph G with ~2.5K vertices and ~250K edges. (The edge weights are all in (0, 1), and the weight of each vertex is derived as the maximum of the ...
1
vote
0answers
65 views

Spread multiple edges by a specified scaled distance (Mathematica 10)

Is there way to spread multiple edges by a specified scaled distance for Graph function in Mathematica 10, something similar to MultiedgeStyle in GraphPlot for example, I would like to write: ...
1
vote
0answers
76 views

Using NMinimize to solve the Multi Commodity Flow problem

I have the following optimization problem and I was hoping to solve it with NMinimize. Unfortunately, I don't get the desired result. I would like to get an optimal vector for $d_{e}$. This is how ...
1
vote
0answers
106 views

Replace part in a matrix that matches specific pattern

I have the following problem. Given a matrix L which looks as follows, Matrix L is a link, route matrix. Further, I got the following vector (d), which indicates the demand per vertex combination. ...
1
vote
0answers
177 views

Triangular lattice with periodic boundary conditions

I am trying to generate an equilateral triangular lattice with fixed vertices and periodic boundary conditions. I am supposed to assign an index (starting from 0) to each vertex in my lattice and then ...
1
vote
0answers
55 views

GraphPlot not working properly

The code ...
1
vote
0answers
58 views

Why does Network`GraphPlot`wrapper appear in my GraphPlot?

I'm making a GraphPlot of data similar to this: ...
1
vote
0answers
52 views

Get correlation matrix when using FindGraphCommunities

Does somebody know how to get the correlation matrix when using FindGraphCommunities (Social Network analysis) using the "Spectra" option? Can somebody tell me as ...
1
vote
0answers
116 views

How to make Layer Directed Graphs (LDG) in mathematica?

I am wondering if I can make a graph like that somehow: I am new to mathematica, I tried to play with Creating a graph with variable size of vertices and variable thickness of edges . I figured if I ...
1
vote
0answers
203 views

How to extract connected bipartite graph from incidence matrix

I'm trying to extract a connected bipartite graph Bconn from the a given incidence matrix B- I have a matrix representing a bipartite graph - the incidence matrix B (weighted or not is unimportant). ...
1
vote
0answers
66 views

GraphHighlightStyle with multiple datasets

I am trying to highlight several subgraphs of a graph using the following command: ...
1
vote
0answers
152 views

Tools for finding minimal or almost-minimal graph vertex colorations in Mathematica v9?

I'm looking to compute minimum vertex colorations (s.t. no two vertices of the same color share an edge: http://en.wikipedia.org/wiki/Graph_coloring) for graphs in Mathematica v9 with potentially up ...
1
vote
0answers
130 views

Network problem of visualization of vertex

I have a question about visualization of network in Mathematica: for example: for this network g = ExampleData[{"NetworkGraph", "Friendship"}]; when we ...
1
vote
0answers
208 views

Get path to end nodes in directed (partially cyclic) graph

I have a large directed graph containing small loops. I would like to extract all paths to all end nodes (no VertexOutComponent) with a given path length $n$. I ...
1
vote
0answers
80 views

What algorithm is Mathematica using for FirstPassageTimeDistribution[]?

What algorithm is Mathematica 9 using for FirstPassageTimeDistribution[]? Is it attempting to use PseudoInverse[] on the ...
0
votes
0answers
57 views

What graph distributions are available in Mathematica?

Where can I find a list of all the graph distributions available in Mathematica?
0
votes
0answers
41 views

Transform NMinimze into LinearProgramming formulation

I have the following maximization problem that I currently try to solve with Minimize/NMinimize. Unfortunately, this kind of solution method takes really long for large systems of equations and ...
0
votes
0answers
38 views

Computing Domination Numbers of Graphs

Is there a way to get Mathematica to compute the domination number (size of the smallest dominating set) of a graph? There doesn't seem to be a direct command for this, so I'm not sure if there would ...
0
votes
0answers
23 views

“Partial” graph layout (with a fixed core)?

Is there a way to apply a graph lay out algorithm to a Graph object in such a way that a subset of its vertices and a subset of its edges are fixed beforehand, and ...
0
votes
0answers
31 views

NMinimize outside the feasible region

I got the following minimization problem. I get a solution if I set constraints1 := L.x >= y; and eliminate constraint 2 from my set of constraints. So ...
0
votes
0answers
73 views

Mathematically Eliminated in Baseball

Earlier today the Yankees were mathematically eliminated from the playoffs. Determining when this condition is satisfied for any given team is complicated but can be solved as a maximum flow problem, ...
0
votes
0answers
48 views

Graph plotting: specify layers for layered drawing

Mathematica can do layered graph drawing with LayeredGraphPlot or GraphLayout -> "LayeredEmbedding". Is it possible to ...