I cannot wrap my head around how the configuration model works if we have a degree sequence that has non-integers in it, i.e. we have edge weights $w\in \mathbb{Q}$ and nost just $w\in \mathbb{N}$ (also see last point of "my research efforts").
The configuration model I know, works like this:
- We have a given graph.
- Cut every edge into two halves, so that only edge stubs (also called "half-edges") are left.
- Choose two stubs uniformly at random and connect them by an undirected edge. Continue with other stub pairs until there are no stubs left (this assumes we start with an even number of edge stubs).
That seems reasonable if we only consider a graph with edge weights equal to $1.0$. But what about when we have edges with weights $3.14$, $2.72$, $1.62$ etc. as is oftentimes the case in real networks. How does the configuration model work out in this case? Take a vertex that has $k_v = 5.86$; now how many edge stubs do we construct for it, $5$ or $6$?
I'm wondering because the modularity formula introduced by Newman here can be used for weighted graphs as well (at least it is used for the Louvain method), but I don't see how the configuration model works in this case.
My research efforts
See the last point for probably the greatest relevance.
- I've seen this paper but I don't think it helps me as they consider degree and vertex strength to be to separate measures with the vertex strength even following a power distribution.
- In his network science book, Albert-László Barabási does not describe the weighted case for the configuration model, just: "The configuration model builds a network whose nodes have pre-defined degrees".
- I've also noticed this paper, but then I don't see how this works: "The network is now formed by paring up stubs with the same weight completely at random." What if we have an edge in our original graph with a unique weight that only appears once in the whole graph?
- Edit: Also in Newman's The structure and function of complex networks, on page 22 (chapter B1 - The configuration model), only integers are used for the degrees: "We choose a degree sequence, which is a set of $n$ values of the degrees $k_i$ of vertices $i = 1 \dots n$, from this distribution. We can think of this as giving each vertex $i$ in our graph $k_i$ "stubs" or "spokes" sticking out of it, which are the ends of edges-to-be."
- ⚠ Edit: I found the Louvain paper references Newman's Analysis of weighted networks, where he writes on page 7: "The same idea can be used to judge community divisions in weighted networks. If we apply our rule for mapping weighted networks to multigraphs, it is straightforward to show that the correct generalization of the modularity is given by precisely the same formula, Eq. (9), provided $A_ij$ represents the weight of the edge between $i$ and $j$, the degree $k_i$ is defined according to Eq. (5), and $m = \frac{1}{2} \sum_{ij} A_{ij}$ as before." That's probably most relevant to my question as I don't see how this is "straightforward".
Earlier on, the method of mapping a weighted network to multigraphs is described like this: "That is, every edge of weight $n$ is replaced with $n$ parallel edges of weight $1$ each, connecting the same vertices. The adjacency matrix of the graph remains unchanged and any techniques that can normally be applied to unweighted graphs can now be applied to the multigraph as well." So, that's basically the answer for this question if we allow integer weights other than $1$. My question is about any weights $w\in \mathbb{Q}$, not just $w\in \mathbb{N}$.