Toy model (SBM)

[skojaku]

Overview

Setting

• We generate a network using the stochastic block model with three blocks, featuring inter-intra edge densities of 0.01 and 0.3 for well-separated communities.
• A random walker has a "state" vector, denoted as $x(t)$, which is initialized to a random unit vector.
• Each edge is associated with a rotation matrix that is applied to the walker's state vector when traversing the edge. This rotation matrix is complementary; when moving from node $i$ to node $j$, rotation matrix $R$ is applied, and its transpose $R^\top$ is applied when moving from $j$ to $i$.

Question

• Under what conditions do the trajectories of the state vector reflect the network's communities?
  • Areas for exploration:
    • Dimension of the state space
    • Coherence between community structure and the assignment of rotation matrices to edges

Coherence Considerations

1. Random case: Each edge has a random rotation matrix independent of the network structure.
2. The most coherent case: No rotation is applied for movements within a community; a random rotation is applied when moving between different communities. Each pair of different community (r,s) has a unique random rotation matrix, which is then assigned to all the edges between communities r and s. Different pairs of communities have different random rotation matrices.

[skojaku]

Results:

Set up

• Dimension of the vector space: 10
• Number of nodes 120
• The adjacency matrix of the base network

Random case

Similarity matrix for the state vectors $x(t)$ over $t \in [1,1000]$. The colors on the top and left bars represent the community membership of the nodes being visited.

The most coherent case

Observation

1. For random case, the trajectories of the state vector appears to be random.
2. For coherent case, the trajectories of the state vector seems to be correlated with the community structure. But there is an interesting pattern. Namely, a. Overall, the state vectors are similar for nodes in the same communities. However, there are also cases, where the nodes in the same communities have dissimilar vectors.

[skojaku]

Intermediate cases:

Set up

• A random rotation matrix is reassigned to each edge with probability $1-\alpha$
• When $\alpha=1$, it is equivalent to the coherent case
• When $\alpha=0$, it is equivalent to the random case

Results

Coherence $\alpha=0.8$

Coherence $\alpha=0.6$

Coherence $\alpha=0.4$

Coherence $\alpha=0.2$

Observation

• Even for relatively coherent cases ($\alpha=0.8,0.6$), we observed a pattern similar to random cases.

[skojaku]

Thought

1. The state vector trajectory accurately represents community structure when there is no rotation within communities and random rotation between them.
2. In this scenario, even if the walker returns to its original community, the state vector may differ based on the paths taken!
3. The state vector $x(t)$ summarizes previous trajectories, which might provide a useful perspective on social balance.
4. Introducing random rotations to a few edges disrupts coherence, resulting in a seemingly random state vector trajectory.

[skojaku]

Code: #2

[rlambiot]

Many thanks for these first experiments!

I have been thinking about it this morning and wondered about the following.

For random walk/diffusive processes:

1. In the case of nsigned network, the archetype for a community would be a connected component. Adding a few edges between the components, we expect the existence of two time scales: a fast scale for the dynamics inside communities, and slow scale for the dynamics across communities.
2. In the case of a signed graph, the archetype for a community would be strong balance: two clusters, with positive edges inside and negative across. In our rotation setting, this would correspond to a rotation of \pi between communities, and rotation of 0 inside the communities. A natural way to add a perturbation to this idealised setting would be to add to each edge a random value for the rotation, e.g. taken from a gaussian with a given \sigma controlling for the importance of noise. When there is no noise, we know that the asymptotic state is one where we have positive values in one cluster, and negative values in the other cluster. If sigma is small enough, the system should rapidly approach this type of configuration ("quasi-stationary state") before slowly approaching the asymptotic state (a vector of zero as the whole graph is not balanced anymore). We would then have a separation of time scales as well.
3. The latter can then be generalised with k groups, e.g. rotations of 2\pi/3 between groups for 3 groups, and the same perturbation scheme can be applied.

[yuoohmaths]

Thanks so much for the report! Very interesting indeed!

Question

• Under what conditions do the trajectories of the state vector reflect the network's communities?

  • Areas for exploration:

  • Dimension of the state space

  • Coherence between community structure and the assignment of rotation matrices to edges

Dimension of an arbitrary value is interesting, and we could also try dimensions of 2 and 3 for proof of concepts.

Coherence Considerations

1. Random case: Each edge has a random rotation matrix independent of the network structure.
2. The most coherent case: No rotation is applied for movements within a community; a random rotation is applied when moving between different communities. Each pair of different community (r,s) has a unique random rotation matrix, which is then assigned to all the edges between communities r and s. Different pairs of communities have different random rotation matrices.

You probably have implemented it but not mentioned it here: for the balanced case, we also have the requirement that the product of the rotation matrices of all cycles is the identity (so e.g., when choosing the rotaiton matrix of $R{31}$, after choosing $R{12}$ and $R_{23}$, we can choose it to make the product identity, depending on how you implement the random walks, instead of choosing randomly).

1. The state vector trajectory accurately represents community structure when there is no rotation within communities and random rotation between them.
2. In this scenario, even if the walker returns to its original community, the state vector may differ based on the paths taken!

Great, it agrees with our theoretical results, though we are more on the other side of when there is no noise, the state vector at stationary should be the same.

3. The state vector $x(t)$ summarizes previous trajectories, which might provide a useful perspective on social balance.
4. Introducing random rotations to a few edges disrupts coherence, resulting in a seemingly random state vector trajectory.

This could integrate with Renaud's comments above -- by considering different scales, short versus long, we can potentially better capture the almost balanced case! One idea from me would be to compute the similarity matrix for $x(t)$ over the period $[0, \Delta t], [\Delta t, 2\Delta t], [2 \Delta t, 3\Delta t], ...$ and see how they changes, but please correct me if I am wrong.

Overall, thanks for the results! I will also explore more -- just wondering whether you have uploaded your code?

[skojaku]

Many thanks for these first experiments!

I have been thinking about it this morning and wondered about the following.

For random walk/diffusive processes:

1. In the case of nsigned network, the archetype for a community would be a connected component. Adding a few edges between the components, we expect the existence of two time scales: a fast scale for the dynamics inside communities, and slow scale for the dynamics across communities.

I may have overlooked something important and would like clarification on this comment. I understand that we are dealing with a discrete-time random walk, where the trajectory in vector space also operates in discrete time. The time scale is consistent both within and across communities. How can I accelerate the time scale within communities? Should I apply the rotation matrix multiple times?

2. In the case of a signed graph, the archetype for a community would be strong balance: two clusters, with positive edges inside and negative across. In our rotation setting, this would correspond to a rotation of \pi between communities, and rotation of 0 inside the communities. A natural way to add a perturbation to this idealised setting would be to add to each edge a random value for the rotation, e.g. taken from a gaussian with a given \sigma controlling for the importance of noise. When there is no noise, we know that the asymptotic state is one where we have positive values in one cluster, and negative values in the other cluster. If sigma is small enough, the system should rapidly approach this type of configuration ("quasi-stationary state") before slowly approaching the asymptotic state (a vector of zero as the whole graph is not balanced anymore). We would then have a separation of time scales as well.

First of all, I'd like to clarify that a random rotation matrix in a high dimensional space is almost a rotation of $\pi/2$. It's not $pi$ though it at least produces communities orthogonal to each other, which are of zero similarities. Do we want to have communities of negative similarities?

Regarding how to add perturbation, I get an overall idea but am not 100% certain how to introduce a gaussian noise on a high-dimensional rotation matrix. Do you mean adding some gaussian noise on the identity matrix (which is zero rotation), and take QR decomposition to generate orthonormal basis (which is Q)?

3. The latter can then be generalised with k groups, e.g. rotations of 2\pi/3 between groups for 3 groups, and the same perturbation scheme can be applied.

Sure!! Will do in the next expreiment.

[skojaku]

Thanks so much for the report! Very interesting indeed!

Question

• Under what conditions do the trajectories of the state vector reflect the network's communities?

  • Areas for exploration:

  • Dimension of the state space

  • Coherence between community structure and the assignment of rotation matrices to edges

Dimension of an arbitrary value is interesting, and we could also try dimensions of 2 and 3 for proof of concepts.

Coherence Considerations

1. Random case: Each edge has a random rotation matrix independent of the network structure.
2. The most coherent case: No rotation is applied for movements within a community; a random rotation is applied when moving between different communities. Each pair of different community (r,s) has a unique random rotation matrix, which is then assigned to all the edges between communities r and s. Different pairs of communities have different random rotation matrices.

You probably have implemented it but not mentioned it here: for the balanced case, we also have the requirement that the product of the rotation matrices of all cycles is the identity (so e.g., when choosing the rotaiton matrix of R 31 , after choosing R 12 and R 23 , we can choose it to make the product identity, depending on how you implement the random walks, instead of choosing randomly).

No, I implemented here without considering balance/imbalance. It's just a more general setting, where a network has a strong communities, and in what condition the trajectories reflect these communities. One of the condition would be via enforcing the balance condition as you mentioned, and I'll check this out in the next experiment!

1. The state vector trajectory accurately represents community structure when there is no rotation within communities and random rotation between them.
2. In this scenario, even if the walker returns to its original community, the state vector may differ based on the paths taken!

Great, it agrees with our theoretical results, though we are more on the other side of when there is no noise, the state vector at stationary should be the same.

Is this "no noise" case is where the edges between communities apply a householder projection to a state vector, and edges within communities apply no transformation?

3. The state vector x ( t ) summarizes previous trajectories, which might provide a useful perspective on social balance.
4. Introducing random rotations to a few edges disrupts coherence, resulting in a seemingly random state vector trajectory.

This could integrate with Renaud's comments above -- by considering different scales, short versus long, we can potentially better capture the almost balanced case! One idea from me would be to compute the similarity matrix for x ( t ) over the period [ 0 , Δ t ] , [ Δ t , 2 Δ t ] , [ 2 Δ t , 3 Δ t ] , . . . and see how they changes, but please correct me if I am wrong.

I'm not sure the question but here is my best guess! The similarity matrix in my results short the similarity over period [0,999]. So similarities of the state vector $x(t)$ for other different period [0, $\delta t$], [$\delta t$, $2\delta t$], [$2\delta t$, $3\delta t$] are on the diagonal block of the similarity matrix in my results.

Overall, thanks for the results! I will also explore more -- just wondering whether you have uploaded your code?

You can find my code in the PR #2 , which is also linked with this Issue thread! You can find the code by looking at the "File Changed" tab in the page. Alternatively, you can open it by switching to the branch the PR is based on.

[yuoohmaths]

Thanks for the replies! It helps a lot clear up my mind!!

• The balanced case could interesting to check!
• For the "no noise" case, I do mean this!
• For the time scales, sorry that I took it wrong, and you are right that it is in the upper left corner! I was thinking of another similarity matrix which can be computed at each time, and the time-scale separation is more evident when you observe different features when t is small versus t is large.
• Thanks for sharing the code!

[hsayama]

Thanks Sadamori and all! Will respond in email.