In the next few paragraphs I want to write about my thoughts and observation about hypergraphs.

Few days ago I decided to read a wikipedia article about hypergraphs and it was very fruitful actually.

I found out that most of my observations can be summed up by this article if read carefully.

https://en.wikipedia.org/wiki/Hypergraph

Hypergraphs definition

A hypergraph is a generalization of a graph in which an edge can connect any number of vertices. Formally, a hypergraph H is a pair H = (X, E) where X is a set of elements called nodes of vertices, and E is a set of non-empty subsets of X called hyperedges or edges.

E is a subset of powerset of X minus empty set.

In a graph, edges are pairs of nodes, in hypergraphs hyperedges can contain an arbitrary number of nodes.

Hypergraphs that have hyperedges of the same cardinality (number of vertices in an edge) are called k-uniform hypergraphs where k is the number of nodes per hyperedge.

An example of a hypergraph, with

\begin{equation} X = \{v_1, v_2, v_3, v_4, v_5, v_6, v_7\} \end{equation}

and

\begin{equation} E = \{e_1,e_2,e_3,e_4\} = \{\{v_1, v_2, v_3\}, \{v_2,v_3\}, \{v_3,v_5,v_6\}, \{v_4\}\} \end{equation}

Hypergraphs can be viewed as incidence structures. In particular, there is a bipartite "incidence graph" or "Levi graph" corresponding to every hypergraph, and conversely, most, but not all, bipartite graphs can be regarded as incidence graphs of hypergraphs.

But what is this incidence structure?

https://en.wikipedia.org/wiki/Incidence_structure

Spodobał mi się fano plane i jego levi graph. Bardzo fajnie to wygląda, ale przez to, że przykład był tylko jeden i to do tego specyficzny, to nie wyrobiłam sobie zbyt dobrej opinii na temat tego jak to właściwie zgeneralizować sobie wewnętrznie.

The 2-section (or clique graph, representing graph, primal graph, Gaifman graph) of a hypergraph is the graph with the same vertices of the hypergraph, and edges between all pairs of vertices contained in the same hyperedge.

Bipartite graph model

A hypergraph H may be represented by a bipartite graph BG as follows: the sets X and E are the partitions of BG, and (x1, e1) are connected with an edge if and only if vertex x1 is contained in edge e1 in H. Conversely, any bipartite graph with fixed parts and no unconnected nodes in the second part represents some hypergraph in the manner described above. This bipartite graph is also called incidence graph.

There is no singular notion of cycles and acyclicity for hypegraphs.

They're different from each other and in some ways counter intuitive.

Maybe I should explore them further for analysis of diffusion?

What to write next?

  1. How to express hypergraphs (incidence structures, bipartite graphs) with examples

Let's imagine that I have some hypergraph.

  1. What is diffusion

https://en.wikipedia.org/wiki/Diffusion

I haven't yet probably studied what diffusion is. I've read about in my statistical phisics book, but it didn't describe whole picture. At least in my opinion.

Diffusion is the net movement of a substance (e.g., an atom, ion or molecule) from a region of high concentration to a region of low concentration. This is also referred to as the movement of a substance down a concentration gradient. A gradient is the change in the value of a quantity (e.g., concentration, pressure, temperature) with the change in another variable (e.g., distance). For example, a change in concentration over a distance is called a concentration gradient, a change in pressure over a distance is called a pressure gradient, and a change in temperature over a distance is a called a temperature gradient.

The word diffusion is derived from the Latin word, "diffundere", which means "to spread out" (if a substance is “spreading out”, it is moving from an area of high concentration to an area of low concentration). A distinguishing feature of diffusion is that it results in mixing or mass transport, without requiring bulk motion (bulk flow). Thus, diffusion should not be confused with convection, or advection, which are other transport phenomena that utilize bulk motion to move particles from one place to another.

Okay, movement of the substance. But what substance exactly?

There are two ways to introduce the notion of diffusion: either a phenomenological approach starting with Fick's laws of diffusion and their mathematical consequences, or a physical and atomistic one, by considering the random walk of the diffusing particles.[1]

In the phenomenological approach, diffusion is the movement of a substance from a region of high concentration to a region of low concentration without bulk motion. According to Fick's laws, the diffusion flux is proportional to the negative gradient of concentrations. It goes from regions of higher concentration to regions of lower concentration. Some time later, various generalizations of Fick's laws were developed in the frame of thermodynamics and non-equilibrium thermodynamics.[2]

From the atomistic point of view, diffusion is considered as a result of the random walk of the diffusing particles. In molecular diffusion, the moving molecules are self-propelled by thermal energy. Random walk of small particles in suspension in a fluid was discovered in 1827 by Robert Brown. The theory of the Brownian motion and the atomistic backgrounds of diffusion were developed by Albert Einstein.[3] The concept of diffusion is typically applied to any subject matter involving random walks in ensembles of individuals.

  1. How I implement my walks and why

So, my walks are implemented as random walks on markov chain. Does it make sense?

I was looking at my resources on that matter:

Spectral Graph Theory and Applications WS 2011/2012 Lecture 5: Random Walks and Markov Chain Lecturer: Thomas Sauerwald & He Sun

And this Thomas Sauerwald is a very interesting folk: http://www.cl.cam.ac.uk/~tms41/

He Sun is also cool: http://people.mpi-inf.mpg.de/~hsun

This can be relevant: http://resources.mpi-inf.mpg.de/departments/d1/teaching/ws11/SGT/index.html

This is the particular lecture:

http://resources.mpi-inf.mpg.de/departments/d1/teaching/ws11/SGT/Lecture5.pdf

What is in this lecture:

  • How to define markov chains.

  • How to walk on a markov chain.

  • How they converge.

  • How to analytically compute results.

and, oh, there is more:

http://resources.mpi-inf.mpg.de/departments/d1/teaching/ws11/SGT/Lecture6.pdf

http://resources.mpi-inf.mpg.de/departments/d1/teaching/ws11/SGT/Lecture7.pdf

Haven't read yet.

A very important special case is the Markov chain that corresponds to a random walk on an undirected, unweighted graph. Here, the random walk picks each step a neighbor chosen uniformly at random and moves to that neighbor. Hence, the transition matrix is

  1. What are my current results
  2. Maybe something about those relevant papers?
In [ ]: