Opinion Dynamics With Decaying Confidence: Application to Community Detection in Graphs

• Irinel-Constantin Morarescu
• Antoine Girard (some supporting slides from 2006. Very helpful!)
• Really important reference: Community detection in graphs.
• Handy chart of symbols, and a bigger chart
• Data sources for the paper:
  • The political blogosphere and the 2004 US election: divided they blog

  • An information flow model for conflict and fission in small groups

• Italics indicate direct quotes
• From the slides, a flock is an entity in a network where the members have agreed upon a direction and a velocity. In the paper, rather than movement vector, the value is an ‘opinion’
• We consider a network of agents where each agent has an opinion. At each time step, the agents exchange their opinion with their neighbors and update it by taking into account only the opinions that differ from their own less than some confidence bound. This confidence bound is decaying: an agent gives repetitively confidence only to its neighbors that approach sufficiently fast its opinion.
  • This seems like a nice way to form bubbles. Agents only see their neighbors and have to accommodate with their neighbors within a narrowing range of acceptance. This means that other agents elsewhere in the network (and depending on the connectivity) would converge differently, and different opinions would be created.
• Under that constraint, global consensus may not be achieved and only local agreements may be reached. The agents reaching a local agreement form communities inside the network.
  • If the decay rate is low enough, then global consensus can be reached. Faster, and the network starts to break apart.
• Our model can be interpreted in terms of opinion dynamics. Each agent has an opinion. At each time step, the agent receives the opinions of its neighbors and then updates its opinion by taking a weighted average of its opinion and the opinions of its neighbors that are within some confidence range of its own. The confidence ranges are getting smaller at each time step: an agent gives repetitively confidence only to the neighbors that approach sufficiently fast its own opinion. This can be seen as a model for a negotiation process where an agent expects that its neighbors move significantly towards its opinion at each negotiation round in order to keep negotiating.
• We assume that the relation is symmetric and anti-reflexive
  • Undirected graph where no nodes are connected to themselves
• This model can be related to the one discussed in [17], [18] where agents harden their position by increasing over time the weight assigned to their own opinion. In our model, the agents implicitly increase also the weights assigned to their neighbors whose opinion converges sufficiently fast to their own opinion, by disregarding the opinions of the other agents. As noticed in [18], hardening the agents positions may hamper the agents to reach an asymptotic consensus. This will be observed in our model as well. However, the aim in this paper is not to exogenously increase the self-confidence of the agents, but to meet a prescribed convergence speed towards the final opinion profile.
  • This last line follows my thinking on bubbles somewhat. I think the hardening is a function of the information distance between the two positions. Convergence can only happen at a certain rate, so the farther apart the harder it is to converge. In this model, that’s done by arbitrarily reducing the confidence, but I think the math should be pretty similar. I do wonder if anti-agreement is useful here.
• our model would coincide with Krause model of opinion dynamics with bounded confidence [9][10][11].
  • It looks like Krause is the fountainhead of this area of research. Lots of really interesting work. Everything seems to be from a perspective that agents will converge on one or more opinions, and then the simulation ends. So I know how to make bubbles (and possibly antibubbles, simply by not having agents ‘harden’). What seems to be missing is the notion in Group Polarization that the opinion becomes more extreme. When searching through the works that cite [9], there does seem to be work in this area, but I wasn’t able to find anything that actually has a model using agent-based simulation.
• In this section, we explore the relation between communities and asymptotically connected components of the network. Let us remark that the set of edges can be classified into two subsets. Intuitively, an edge E(finite)is in if the agents and stop interacting with each other in finite time. E(infinite)consists of the interactions between agents that are infinitely recurrent.
  • So this works in the context that the final opinion is static. I think opinions need a random walk component. Given that there are multiple opinions, is the difference a hypotenuse or manhattan distance?
  • As discussed in the the end of the simulation, any connected agents must be in agreement. That means that you can just look at the connections and determine the group?
• Asymptotic Agreement Implies Asymptotic Connectivity
  • They show that this holds for most but not all conditions. That’s an interesting finding, since it implies in almost any sufficiently connected network, a bubble will engulf most individuals that agree…
  • In this section, we showed that asymptotic connectivity of agents implies asymptotic agreement and that under additional reasonable assumptions these are actually equivalent except for a set of vectors of initial opinions of Lebesgue measure 0. In other words, we can consider almost surely that the communities of agents correspond to the connected components of the graph G(infinity). I think this agrees with my above point.
• Community Detection: In the usual sense, communities in a graph are groups of vertices such that the concentration of edges inside one community is high and the concentration of edges between communities is comparatively low. Because of the increasing need of analysis tools for understanding complex networks in social sciences, biology, engineering or economics, the community detection problem has attracted a lot of attention in the recent years. The problem of community detection is however not rigorously defined mathematically. One reason is that community structures may appear at different scales in the graph: there can be communities inside communities. Another reason is that communities are not necessarily disjoint and can overlap. We refer the reader to the excellent survey [12] and the references therein for more details. Some formalizations of the community detection problem have been proposed in terms of optimization of quality functions such as modularity [13] or partition stability [14].
• Essentially, the modularity Q(P)of the partition P is the proportion of edges within the classes of the partition minus the expected proportion of such edges, where the expected number of edges between vertex i and j is assumed to be (degree_i*degree_j)/(all edges)
• The higher the modularity, the better the partition reflects the community structure of the graph. Thus, it is reasonable to formulate the community detection problem as modularity maximization. However, it has been shown that this optimization problem is NP-complete [21]. Therefore, approaches for community detection rely mostly on heuristic methods. In [15], a modularity optimization algorithm is proposed based on spectral relaxations. Using the eigenvectors of the modularity matrix, it is possible to determine a good initial guess of the community structure of the graph. Then, the obtained partition is refined using local combinatorial optimization. In [16], a hierarchical combinatorial approach for modularity optimization is presented. This algorithm which can be used for very large networks, is currently the one that obtains the partitions with highest modularity.
• Bubbles at scales? “Stability measures the quality of a partition by giving a positive contribution to communities from which a random walker is unlikely to escape within the given time scale. For small values of t, this gives more weights to small communities whereas for larger values of t , larger communities are favored. Thus, by searching the partitions maximizing the stability for several values of , one can detect communities at several scales.“
• The algebraic connectivity of a graph G is the second-smallest eigenvalue of the Laplacian matrix of G
• we want to find groups of vertices that are more densely connected than the global graph. This coincides with the notion of community. The larger δ, the more densely connected the communities. This makes it possible to search for communities at different scales of the graph.
• For each combination of parameter value, the model was simulated for 1000 different vectors of initial opinions chosen randomly in [0,1]³⁴. Simulations were performed as long as enabled by floating point arithmetics.
  • I think that this means that each agent was given a distinct random opinion for each of 1,000 runs. Then they looked for the most common clusterings
• It is interesting to remark that for δ = 2 we almost obtained the communities that were reported in the original study [23]. Only one agent has been classified differently.
• When δ increases, the communities become smaller but more densely connected.
  • It should be very interesting to look at belief velocity at different scales.
• …for the same value of parameter δ, the modularity is very similar for all partitions. Actually, all the partitions obtained for the same value of δ are almost the same. As in the previous example, we can see that the choice of parameters R and α affects the probability of obtaining a given partition. The partition with maximal modularity is obtained for δ = 0.2, it is a partition in 4 communities with modularity 0.523
  • I would love to see the distribution here. Something like a confidence interval might be nice to use to show that these are not due to chance. Here’s a paper on how to compare: Network-based statistical comparison of citation topology of bibliographic databases 
• Let us remark that even though the information on the political alignment of the books is not used by the algorithm, our approach allows to uncover this information. Indeed, for δ = 0.1, we obtain 2 communities that are essentially liberal and conservative. For δ = 0.2, we then obtain 4 communities: liberal, conservative, centrist-liberal, centrist-conservative.
  • Note that this is information appears to be latent
• The last example we consider consists of a significantly larger network of 1222 political blogs [24]. In this network, an edge between two vertices means that one of the corresponding blogs contained a hyperlink to the other on its front page. We also have the information about the political alignment of each blog based on content: 636 are conservative, 586 are liberal.
• There are 2 main communities: one with 653 blogs, from which 94% are conservative, and one with 541 blogs, from which 98% are liberal. The 28 remaining blogs are distributed in 10 tiny communities. When we progressively increase δ, we can see that the size of the two large communities reduces moderately but progressively until δ = 0.65 where the conservative community splits into several smaller communities, the largest one containing 40 blogs. The liberal community remains until δ = 0.725 where it splits into smaller communities, the largest one containing 54 blogs.
  • The paper they are using for the data was published in 2005,  and they were collecting their data in 2004-2005. (DailyKos and powerlineblog from 1 Jan 2005)