4 ms·

This may be a tangent, but I feel like pointing out that I, for one, have recently become more aware of the fact that a graph is really just a binary relation.

by theoh 10y ago

This may be a tangent, but I feel like pointing out that I, for one, have recently become more aware of the fact that a graph is really just a binary relation. This is not discussed much in all the talk about social networks. It's always the graph (the "one") that's foregrounded, rather than the multiplicity of edges, each a relation. I know this is mathematically an obvious thing, but surely the relational perspective is more amenable to generalization. We should make more of it.

swsieber 10y ago
Mostly, if you cant have multiple edges, that is true. If you can't represent some well in a graph because it's too messy, you could try using an adjacency matrix, along with a clustering algorithm to figure out how to order the columns / rows.
- theoh 10y ago
  Actually, if you consider each edge as an entity, you can represent multiple edges using the relation incident(Node, Edge). This is analogous to using an incidence matrix. It also works for hypergraphs.
macawfish 10y ago
If you're thinking of weighted, directed graphs, a binary relation doesn't quite fully represent it. In the weighted directed case, a graph is a function from Nodes × Nodes → Weights, (where Weights ⊆ ℤ or Weights ⊆ ℝ or something like that)... Which makes weighted graphs perfect for representation by matrices! Studying adjacency matrix of weighted, directed graphs gave me a profound realization matrices are a table of relationships between their "dimensions". I never looked at matrices the same way again. I realized that the identity column was literally the entries that represented a relationship between a dimension/node and itself. I went down many rabbit holes... particularly the question of graph isomorphism. That problem is a rabbit hole. Another rabbit hole is the Hamiltonian cycle problem. P.S. check out hypergraphs, which are not necessarily binary relations and generalize graphs. Incidentally, hypergraphs have an adjacency tensor. I've started to understand that tensors are like 'tables' of relationships between dimensions + dimensions representing some or all of their possible combinations. By the way, if you can figure out a way to do fast multiplication of matrices over degree-truncated polynomial rings, I'll show you a fast way to count the number of hamiltonian cycles in a graph. These problems are intricately linked.
- theoh 10y ago
  Sometimes the matrix, like for example the adjacency matrix for Wikipedia internal links, will be very sparse. Another reason to use relations rather than an inefficient, mostly empty implicit data structure. That Wikipedia adjacency matrix would be interesting to visualize, though. There are tools out there for visualizing sparse matrices as graphs: http://yifanhu.net/GALLERY/GRAPHS/ http://yifanhu.net/GALLERY/GRAPHS/
  - maweki 10y ago
    "using relations" or a particular data structure wasn't at all the point of this particular discussion. The point was that, for a simple directed graph, the edges represent a binary relationship. While for a weighted directed graph, it represents a relationship-matrix. For the graph being non-directed this would mean, that the relationship(-matrix) is symmetric. Meaning that any algebra, algorithm, proof, etc. on graphs of that type can be applied for the other interpretation as well. Implementation is a different question. "Most" binary relations we happen upon (less-than as the obvious) have an infinite domain and infinite cardinality (when represented as a set of tuples), making it very hard to "visualize" as a graph.
    - macawfish 10y ago
      Your last sentence is pretty much a summary of my attempt to understand the amplituhedron, and as far as I've gottan
  - rspeer 10y ago
    I've never seen a visualization of a graph at the scale of Wikipedia that conveys anything useful in the visualization. You just get a big hairball.
    - theoh 10y ago
      Yeah, actually that page has a Wikipedia graph on it which looks exactly like a spiky sun. I'd like to see more work like the paper from a few years ago which ran PageRank and HITS on Wikipedia to discover the most central pages. The PageRank result indicated church hierarchy and nation states were important, while HITS had things like "television" "animal" as the most authoritative/central pages. There is so much structure there to be investigated.

by theoh 10y ago

swsieber 10y ago

Mostly, if you cant have multiple edges, that is true. If you can't represent some well in a graph because it's too messy, you could try using an adjacency matrix, along with a clustering algorithm to figure out how to order the columns / rows.

theoh 10y ago
Actually, if you consider each edge as an entity, you can represent multiple edges using the relation incident(Node, Edge). This is analogous to using an incidence matrix. It also works for hypergraphs.

macawfish 10y ago

If you're thinking of weighted, directed graphs, a binary relation doesn't quite fully represent it. In the weighted directed case, a graph is a function from Nodes × Nodes → Weights, (where Weights ⊆ ℤ or Weights ⊆ ℝ or something like that)... Which makes weighted graphs perfect for representation by matrices! Studying adjacency matrix of weighted, directed graphs gave me a profound realization matrices are a table of relationships between their "dimensions". I never looked at matrices the same way again. I realized that the identity column was literally the entries that represented a relationship between a dimension/node and itself. I went down many rabbit holes... particularly the question of graph isomorphism. That problem is a rabbit hole. Another rabbit hole is the Hamiltonian cycle problem. P.S. check out hypergraphs, which are not necessarily binary relations and generalize graphs. Incidentally, hypergraphs have an adjacency tensor. I've started to understand that tensors are like 'tables' of relationships between dimensions + dimensions representing some or all of their possible combinations. By the way, if you can figure out a way to do fast multiplication of matrices over degree-truncated polynomial rings, I'll show you a fast way to count the number of hamiltonian cycles in a graph. These problems are intricately linked.

theoh 10y ago
Sometimes the matrix, like for example the adjacency matrix for Wikipedia internal links, will be very sparse. Another reason to use relations rather than an inefficient, mostly empty implicit data structure. That Wikipedia adjacency matrix would be interesting to visualize, though. There are tools out there for visualizing sparse matrices as graphs: http://yifanhu.net/GALLERY/GRAPHS/ http://yifanhu.net/GALLERY/GRAPHS/
- maweki 10y ago
  "using relations" or a particular data structure wasn't at all the point of this particular discussion. The point was that, for a simple directed graph, the edges represent a binary relationship. While for a weighted directed graph, it represents a relationship-matrix. For the graph being non-directed this would mean, that the relationship(-matrix) is symmetric. Meaning that any algebra, algorithm, proof, etc. on graphs of that type can be applied for the other interpretation as well. Implementation is a different question. "Most" binary relations we happen upon (less-than as the obvious) have an infinite domain and infinite cardinality (when represented as a set of tuples), making it very hard to "visualize" as a graph.
  - macawfish 10y ago
    Your last sentence is pretty much a summary of my attempt to understand the amplituhedron, and as far as I've gottan
- rspeer 10y ago
  I've never seen a visualization of a graph at the scale of Wikipedia that conveys anything useful in the visualization. You just get a big hairball.
  - theoh 10y ago
    Yeah, actually that page has a Wikipedia graph on it which looks exactly like a spiky sun. I'd like to see more work like the paper from a few years ago which ran PageRank and HITS on Wikipedia to discover the most central pages. The PageRank result indicated church hierarchy and nation states were important, while HITS had things like "television" "animal" as the most authoritative/central pages. There is so much structure there to be investigated.