  Attitudinal Network Graphs are signed graphs where edges capture an expressed
opinion; two vertices connected by an edge can be agreeable (positive) or
antagonistic (negative). A signed graph is called balanced if each of its
cycles includes an even number of negative edges. Balance is often
characterized by the frustration index or by finding a single convergent
balanced state of network consensus. In this paper, we propose to expand the
measures of consensus from a single balanced state associated with the
frustration index to the set of nearest balanced states. We introduce the
frustration cloud as a set of all nearest balanced states and use a
graph-balancing algorithm to find all nearest balanced states in a
deterministic way. Computational concerns are addressed by measuring consensus
probabilistically, and we introduce new vertex and edge metrics to quantify
status, agreement, and influence. We also introduce a new global measure of
controversy for a given signed graph and show that vertex status is a zero-sum
game in the signed network. We propose an efficient scalable algorithm for
calculating frustration cloud-based measures in social network and survey data
of up to 80,000 vertices and half-a-million edges. We also demonstrate the
power of the proposed approach to provide discriminant features for community
discovery when compared to spectral clustering and to automatically identify
dominant vertices and anomalous decisions in the network.
