1 Introduction

Non-additive measures are monotonic set functions. They generalize additive measures as e.g. probabilities and the Lebesgue measure. Several names are used to represent this concept; they are also called fuzzy measures (name introduced by Sugeno in 1972 [18, 19]), capacities (see e.g. Choquet’s seminal work [7]) and monotonic games (see e.g. [24]).

Non-additive measures can be used for representing uncertainty. In this case, several families of measures have been defined, see e.g. probabilities, belief and plausibility, as well as possibility and necessity. It is usual to use functions to combine and aggregate these uncertainty measures. For instance, the Demspter-Shafer rule of combination is used for belief measures.

Non-additive measures are also used to represent importance or relevance of information sources in data aggregation [5, 11, 23]. This is the case when we use the Choquet [7] and the Sugeno integral [19]. These integrals aggregate a set of values proceeding from a set of information sources taking into account the relevance of the sources. Non-additive measures are used to represent our background knowledge on this relevance of the sources. The measures permit us to have more flexibility than the one offered by additive measures. They do not longer require that the measure of a set is the addition of the measure of its components. This permits to represent positive and negative interaction of the elements. That is, we can have for two disjoint sets A and B (i.e., \(A \cap B = \emptyset \)) that either \(\mu (A \cup B) > \mu (A) + \mu (B)\), \(\mu (A \cup B) < \mu (A) + \mu (B)\) or just \(\mu (A \cup B) = \mu (A) + \mu (B)\) as it is the case for probabilities.

Fig. 1.
figure 1

Visualization of Example 1 where the difference between measures are represented by means of thickness.

Full size image

This additional flexibility is at the cost of a more complex definition. As non-additive measures do not satisfy the additivity axiom, we need to supply values for each subset of the reference set. Being a set function, this means that we need to supply \(O(2^n)\) where n is the number of elements of the reference set.

In order to help in the definition of these measures, a few families of measures have been defined with reduced complexity. This is the case of Sugeno \(\lambda \)-measures [19], \(\bot \)-decomposable fuzzy measures, hierarchically decomposable fuzzy measures [22], distorted and m-dimensional distorted probabilities [14], k-additive measures [10]. There have also been approaches to learn these measures from data. This is the case of e.g. [1, 16].

Due to the number of parameters needed to define these measures, it is also difficult to understand what exactly represents a fuzzy measure. For this purpose, several (mathematical) indices can be used. The Shapley [17] and Banzhaf [3] indices are two of them.

In this paper we propose and explore an alternative way to understand these type of measures using graphical representations of the measures. As we will discuss later, our proposal is based on graph visualizations, in particular, node-link diagram representations.

Node-link diagrams [4, 13, 20] (see e.g. Fig. 1) are widely used to draw relationships between elements in a model. They are used in social networks, process models, and on hierarchical structures [6]. This type of graphs depict a collection of elements (vertices or nodes) and a set of relations between them (edges). Edges may indicate a weight (such as the strength of the relationship), as well as the direction of the relationship between the nodes. It is easier to read and understand node-link diagrams when the underlying relations are simple and sparse [8], however, they are less preferred with many overlapping links, that can generate occlusion problems [4]. The interpretation of the nodes’ and links’ depends on the application. In fact, one prior user study depicting multivariate data sets [2] gave weights to the links with selected visual cues to better understand the relationships’ strength. Using similar principles, in this paper we propose the use of brightness and width to better understand and emphasize the relationships of discrete non-additive measures.

The problem of visualizing non-additive measures have also been considered by Murofushi’s lab [15, 21, 25]. They have also used graphs to represent fuzzy measures (Hasse diagrams). As we do here, nodes represent subsets \(A \subseteq X\). Then, [15] locates the nodes in the picture taking into account the measure of the sets. In [15] they use a combinatorial optimization problem with exhaustive search to determine the position of the nodes in the picture. In [25] they use a branch and bound algorithm for the same purpose. Their approach is different to our approach here where measures are represented by brightness and width of the edges.

The structure of the paper is as follows. In Sect. 2 we review some basic definitions that we need in this paper. Section 3 introduces our approach for visualizing the measures and Sect. 4 provides visualization examples. The paper finishes with a summary and lines for future work.

2 Preliminaries

In this section we review the definition of non-additive measures. We also give the definition of the Choquet integral, one of the tools used to aggregate data from a set of information sources with respect to the non-additive measure.

Definition 1

A non-additive (or fuzzy) measure \(\mu \) on a set X is a set function \(\mu : \wp (X) \rightarrow [0,1]\) satisfying the following axioms:

  1. (i)

    \(\mu (\emptyset ) = 0\), \(\mu (X) = 1\) (boundary conditions)

  2. (ii)

    \(A \subseteq B\) implies \(\mu (A) \le \mu (B)\) (monotonicity)

Here, \(\wp (X)\) represents the power set of X.

Note that in this definition the additivity axiom \(\mu (A\cup B)=\mu (A) + \mu (B)\) for \(A \cap B=\emptyset \) is replaced by the monotonicity condition.

Given a set of information sources X (e.g., sensors or experts) we can represent the value supplied by each information source x in X by f(x). Then, \(\mu \) represents the importance of the sets \(A \subseteq X\). That is, \(\mu \) represents the importance of a set A of information sources.

When the additivity takes place, we have that the importance of a set corresponds to the addition of the importance of its terms. That is \(\mu (A)=\sum _{x \in A} \mu (\{x\})\). As this is no longer a requirement we may represent positive interactions between elements and negative interactions. Note that we have a positive interaction between A and B (with \(A \cap B=\emptyset \)) when

$$\begin{aligned} \mu (A \cup B) > \mu (A) + \mu (B) \end{aligned}$$

and that we have a negative interaction when

$$\begin{aligned} \mu (A \cup B) < \mu (A) + \mu (B). \end{aligned}$$

A well known example of a non-additive measure is the one introduced in [9]. This example is about the evaluation of students of a high school in terms of their ratings in three subjects: mathematics, physics, and literature. The importance of these subjects is expressed by means of a measure. We revise this example below as we will use it for illustration in this paper. The formulation follows [23].

Table 1. Non-additive measure of Example 1 based on [9].
Full size table

Example 1

The director of a high school has to evaluate the students according to their level in mathematics (M), physics (P), and literature (L). The evaluation consists of obtaining a final rating as an average of the ratings of the three subjects. For each student, the final rating depends on the importance given to the subjects. To settle these importances, a non-additive measure is used. Here, X is the set of all subjects (i.e., \(X = \{M, P, L\}\)), and \(\mu (A)\) is the importance of a particular set of subjects A. The definition of the measure considers the following elements.

  1. 1.

    Boundary conditions:

    \(\mu (\emptyset )=0\), \(\mu (\{M,P,L\})=1\)

    The importance of the empty set is 0. The set consisting of all objects has maximum importance.

  2. 2.

    Relative importance of scientific versus literary subjects:

    \(\mu (\{M\})=\mu (\{P\})=0.45\), \(\mu (\{L\})=0.3\)

    The importance of mathematics and physics is greater than the importance of literature.

  3. 3.

    Redundancy between mathematics and physics:

    \(\mu (\{M,P\})=0.5 < \mu (\{M\}) + \mu (\{P\})\)

    Mathematics and physics are similar subjects. The importance of the set containing both should not be larger than their addition.

  4. 4.

    Support between literature and scientific subjects:

    \(\mu (\{M,L\})=\mu (\{P,L\})=0.9 > \mu (\{P\}) + \mu (\{L\}) = 0.45+0.3 = 0.75\)

    \(\mu (\{M,L\})=\mu (\{P,L\})=0.9 > \mu (\{M\}) + \mu (\{L\}) = 0.45+0.3 = 0.75\)

    Mathematics and literature are complementary subjects.

An outline of this fuzzy measure is given in Table 1.

In this example we have seen that mathematics and literature have positive interaction while mathematics and physics have negative interaction. One of the ways to observe the positive interaction is by means of the Möbius transform.

The Möbius transform of a non-additive measure on X is a set function that assigns to each subset of X a value (either positive or negative). For each non-additive measure there is a unique Möbius transform, and for each Möbius transform there is a unique measure. Formally, a Möbius transform is a function \(m: \wp (X) \rightarrow {\mathbb {R}}\) such that \(m(\emptyset )=0\), \(\sum _{A \subseteq X} m(A)=1\), and, if \(A \subset B\), then \(\sum _{C \subseteq A} m(C) \le \sum _{C \subseteq B} m(C)\). The following definition explains how to build the Möbius transform from a measure.

Definition 2

Let \(\mu \) be a fuzzy measure; then, its Möbius transform m is defined as

$$\begin{aligned} m_{\mu }(A) := \sum _{B \subseteq A} (-1)^{|A|-|B|} \mu (B) \end{aligned}$$
(1)

for all \(A \subset X\).

Note that the function m is not restricted to the [0, 1] interval.

Given a function m that is a Möbius transform, we can reconstruct the original measure as follows:

$$\begin{aligned} \mu (A) = \sum _{B \subseteq A} m(B) \end{aligned}$$

for all \(A \subseteq X\).

Table 2 gives the Möbius transform of the measure in Example 1 and outlined in Table 1.

Table 2. Möbius transform of the measure given in Example 1 and summarized in Table 1.
Full size table

Given an assignment \(f: X \rightarrow {\mathbb {R}}\) (that assigns a value to each information source), and a non-additive measure \(\mu \) we can aggregate the values f(x) for \(x \in X\) by means of a Choquet integral. In Example 1 this means that given a student and three marks one for mathematics, another for physics and a third for literature, we can average them and obtain an aggregated value taking into account the importances of these subjects according to the measure \(\mu \). For illustration, we give the definition of the Choquet integral below.

Definition 3

Let \(\mu \) be a non-additive measure on \(X=\{x_1, \dots , x_N\}\); then, the Choquet integral of a function \(f: X \rightarrow \mathbb {R}^{+}\) with respect to the fuzzy measure \(\mu \) is defined by

$$\begin{aligned} (C)\int f d \mu = \sum _{i=1}^N [f(x_{s(i)}) - f(x_{s(i-1)})] \mu (A_{s(i)}), \end{aligned}$$
(2)

where \(f(x_{s(i)})\) indicates that the indices have been permuted so that \(0 \le f(x_{s(1)}) \le \dots \le f(x_{s(N)}) \le 1\), and where \(f(x_{s(0)})=0\) and \(A_{s(i)}=\{x_{s(i)}, \dots , x_{s(N)}\}\).

An important property of the Choquet integral is that when the measure is additive it corresponds to the Lebesgue integral. In other words, when the measure is a probability, the Choquet integral corresponds to the weighted mean of the values (where the weights corresponds to the probabilities).

3 Our Approach

In order to visualize graphically a non-additive measure, we first build a graph from the measure, and then we use node-link diagrams to depict the graph. It is well known that a graph consists of nodes or vertices – basic elements–, and edges – relationships between these elements–. That is, a graph G is defined by the pair \(G=(V,E)\) where V is the set of vertices and \(E \subset V \times V\) is the set of edges. In our case, we consider labeled graphs where both vertices and edges have a label. So, in addition to V and E we have also two label functions \(l_V\) and \(l_E\).

The construction of a graph for a non-additive measure \(\mu \) on the reference set X is as follows.

  • Define the set of vertices as the subsets of X excluding the empty set. That is, \(V=\wp (X) \setminus \emptyset \).

  • Define the set of edges in terms of set inclusion on \(\wp (X)\) between sets that only differ in one element. That is,

    $$\begin{aligned} E = \cup _{a \subset X, c \notin a} \{(a,a \cup c)\}. \end{aligned}$$

  • Assign to each vertex the Möbius transform of the corresponding set. That is, \(l_V(A)=m(A)\).

  • Assign to each edge (a, b) the difference between the measure on the largest set and the measure on the smallest set. That is, for (a, b) with \(a \subset b\) define \(l_E((a,b))=\mu (b)-\mu (a)\).

Then, we depict this graph using a node-link diagram, that is, we represent each vertex (i.e., the corresponding subset of X and its Möbius transform) and the edges (i.e., the difference between the values of the non-additive measures \(l_E((a,b))\)). We have considered two graphical representations for \(l_E\). In one case this information is depicted by brightness. The values of brightness range from 0.0 to 0.9, where the value 0.0 represents the biggest difference (darker blue), and 0.9 the smallest difference (brighter blue). Then, we transform the difference between values (say d) into brightness using \(1-d\). In the other case, we use the thickness of the link between the nodes for depicting \(l_E\).

Table 3. Labelling function for the graph constructed for Example 1 and summarized in Table 1.
Full size table
Fig. 2.
figure 2

Visualization of Example 1 where the difference between measures are represented by means of brightness. (Color figure online)

Full size image

To illustrate this construction, we consider the non-additive measure in Example 1. The graph contains 7 nodes corresponding to the subsets of \(X=\{M,L,P\}\). That is,

$$\begin{aligned} V=\{\{M\}, \{P\}, \{L\}, \{M,L\}, \{M,P\}, \{P,L\}, \{M,P,L\}\}. \end{aligned}$$

Edges will be defined for \((M,ML), (M,MP), (P,PL), (P,MP), (L,PL), (L,MPL)\), (MP, MPL), (PL, MPL), (ML, MPL). Then, \(l_V\) is defined for each node according to Table 2. Finally, \(l_E\) is defined according to Table 3. As an example, we give the computation of \(l_E((M,ML))\) and \(l_E((M,MP))\). We use MP to represent the set \(\{M,L\}\).

$$\begin{aligned} l_E((M,ML))=\mu (ML)-\mu (M)= 0.9 - 0.45 =0.45 \end{aligned}$$
$$\begin{aligned} l_E((M,MP))=\mu (MP)-\mu (M)= 0.5 - 0.45 =0.05 \end{aligned}$$

Figures 1 and 2 represent this graph. Figure 2 corresponds to the case of using brightness. For instance, \(l_E\) of the edge (L, PL) is 0.60 and thus a high value (therefore, it is depicted by a dark edge), while the \(l_E\) of the edge (PL, MPL) is 0.1 (therefore, it is shown with a brighter edge). The default value of the edge’s width was 0.43px and hue valued 240 from the HSB model. So, the visualization shows with dark arrows when the measure increase is significant. We can also see that the measure of \(\{M,P\}\) is not changed much with respect to the one of \(\{M\}\) and \(\{P\}\) (all inputs have arrows with light colours) and this causes that the Möbius transformation is negative. In contrast, \(\{M,L\}\) and \(\{P,L\}\) receive two dark arrows and the Möbius is positive.

Figure 1 corresponds to the use of thickness to represent the difference between measures. However, it may be perceptually challenging to differentiate between edges with similar thickness values. Thus, we suggest to utilize brightness to encode differences between measures in the next section. Brightness, as well as hue and width, has been used previously for encoding correlation degree in graphs, see e.g. [12].

4 Examples of Visualizations

In this section we present the visualization of another measure that contains five elements, and thus, more relationships. It is a hierarchically decomposable fuzzy measure (see [22] for details) that is based on the structure represented in Fig. 3.

Fig. 3.
figure 3

Graphical representation of a hierarchical decomposable fuzzy measure on the reference set \(\{T,M,P,L,G\}\). The reference set contains two subjects for humanities (literature and classical greek) and three scientific subjects (topology, mathematics and physics).

Full size image
Fig. 4.
figure 4

Visualization of the hierarchical decomposable fuzzy measure. (Color figure online)

Full size image
Fig. 5.
figure 5

Visualization of the hierarchical decomposable fuzzy measure. (Color figure online)

Full size image

The measure is similar to the one of Example 1, but the reference set includes five subjects instead of three. There are three scientific subjects: mathematics (M), physics (P) and topology (T – in fact, in the original example this is mathematical logics but we use T here for convenience), and two humanistic subjects: literature (L) and greek (G). The measure has some similarities to Example 1 as scientific subjects have more weight than humanistic ones, and interactions between scientific and humanistic are positive while interactions between scientific subjects, and interactions between humanistic are negative.

In this sense note that the Möbius transform can be misleading as \(m(\{T,P,M\})=0.35\) but \(\mu (\{T,P,M\})=0.50\) with \(\mu (\{T,P\})=\mu (\{T,M\})=\mu (\{P,M\})=0.47\).

Two visualizations of this measure are given in Fig. 4. Both describe the information by means of the brightness of the colour. One uses standard arrows and the other uses tapered arrows. In this case, the nodes contain the value of the measure for the set (instead of the Möbius transform). Again, we can see the most significant changes.

Figure 5 gives another representation of the measure. In this case, only the edges with a significant difference between measures are shown (i.e., a difference larger than 0.1). The nodes include the Möbius transform. The brightness of the edges is in relation to the difference. Finally, for each edge we have a label corresponding to the element that we are adding. That is, in the edge between \(\{T,P,M\}\) and \(\{T,P,M,G\}\) we have the label G.

5 Future Work

In this paper we have suggested and explored the visualization of non-additive measures using node-link diagrams. Future work will focus on evaluating the initiatives presented here with users, as well as developing alternative ways for visualizing discrete non-additive measures including, e.g., other indices. For instance, the size of the nodes could encode the Möbius transformation. Moreover, we plan to look at measures on larger sets, and use other tools to build the visualizations, exploring, for example, the use of hypergraphs. We will also explore visualization tools for measures on larger sets, and see if our approach scales well or alternative tools are needed.