A Review on Quantification Learning <s> NETWORK QUANTIFICATION <s> The increasing availability of participatory web and social media presents enormous opportunities to study human relations and collective behaviors. Many applications involving decision making want to obtain certain generalized properties about the population in a network, such as the proportion of actors given a category, instead of the category of individuals. While data mining and machine learning researchers have developed many methods for link-based classification or relational learning, most are optimized to classify individual nodes in a network. In order to accurately estimate the prevalence of one class in a network, some quantification method has to be used. In this work, two kinds of approaches are presented: quantification based on classification or quantification based on link analysis. Extensive experiments are conducted on several representative network data, with interesting findings reported concerning efficacy and robustness of different quantification methods, providing insights to further quantify the ebb and flow of online collective behaviors at macro-level. <s> BIB001 </s> A Review on Quantification Learning <s> NETWORK QUANTIFICATION <s> In many real-world applications there is a need to monitor the distribution of a population across different classes, and to track changes in this distribution over time. As an example, an important task is to monitor the percentage of unemployed adults in a given region. When the membership of an individual in a class cannot be established deterministically, a typical solution is the classification task. However, in the above applications the final goal is not determining which class the individuals belong to, but estimating the prevalence of each class in the unlabeled data. This task is called quantification. Most of the work in the literature addressed the quantification problem considering data presented in conventional attribute format. Since the ever-growing availability of web and social media we have a flourish of network data representing a new important source of information and by using quantification network techniques we could quantify collective behavior, i.e., the number of users that are involved in certain type of activities, preferences, or behaviors. In this paper we exploit the homophily effect observed in many social networks in order to construct a quantifier for networked data. Our experiments show the effectiveness of the proposed approaches and the comparison with the existing state-of-the-art quantification methods shows that they are more accurate. <s> BIB002
Given a network G represented by an indirect graph, G (V , E, L ), defined by the set of nodes (V ), the set of edges (E), and the set of classes (L ), the objective of network quantification methods is to exploit this information to estimate the prevalence of the classes in L . BIB001 presents the first method for network quantification. Besides applying most of the approaches based on Classify, Count, & Correct (see Section 6), the authors introduce a Link-Based Quantifier (LBQ) to exploit the homophily (i.e., "love of the same") effect that can be observed in many social networks. Inspired by the main relation of binary quantification (30), the connections of each network node are modeled using a mixture of two distributions conditioned on both classes. The probability that a node in V is connected to a given node v can be estimated as in which P (v |+) and P (v |−) are the probability of a connection to v from a positive and a negative node, respectively. Note that P (v), P (v |+), and P (v |−) can be easily obtained from G. Solving for p, we have that if P (v |+) P (v |−). Based on this expression, LBQ algorithm works as follows: (i) compute (84) for all unlabelled nodes in V ; (ii) discard those nodes in which the value of p falls outside the range [0, 1]; and (iii) the estimate of the prevalence,p, is the median of the valid values obtained. For instance, in the example depicted in Figure 6 (a), the computation of Equation (84) for node A is p = 4/12−1/5 3/5−1/5 = 0.33. To solve the lack of information due to a low connectivity in G, steps 1 and 2 are repeated for several k-hop neighborhoods. The k-hop neighborhood of node v is the set of vertices that are reachable from v in k hops or fewer. According to the authors, k ≤ 3 generates enough valid estimates due to the small-world effect observed in many networks. The computation of Equation (84) with k = 2 for node A is p = 4/12−3/5 4/5−3/5 = −1.33, and the value is discarded because it falls outside [0, 1]. The major issue of the LBQ method BIB002 ) is that there is no guarantee that estimates for all classes sum to 1. In the experiments in BIB001 , the prevalence is computed only for the positive class, assigning the complementary to the negative class, [p, 1 −p]. However, the class distribution may vary if the algorithm is applied to the negative class, [1 −n,n] [p, 1 −p]. BIB002 propose also two groups of techniques for network quantification to exploit the homophily effect. The main idea is to divide the network into several sub-networks to better bound homophily. Two different partitioning strategies are studied: community discovery and khop neighborhoods, also called ego-networks in this article. The methods based on community discovery have two steps: (i) to find a group of communities and (ii) to assign a class to unlabeled nodes. Any community discovery algorithm can be applied for the first step. The class assigned is the one with highest frequency in the community to which the unlabeled node belongs. However, some community discovery algorithms return overlapping communities. In such cases, the authors propose two strategies to select the class for a given node: (i) frequency based: assigning the class with the highest relative frequency considering all the communities of the node; and (ii) density based: assigning the highest frequency class of the node's denser community (in terms of graph connectivity). In the example of Figure 6 (b), node B only belongs to community C3 with class frequencies [ 2 3 , 1 3 ], so the label assigned is +1. In the case of node A that belongs to communities C1 and C2, the class assigned depends on the strategy: Using frequency based, the class selected is −1, because its frequency in C2 is 3 4 , while the frequency of class +1 in C1 is 2 3 . Applying a density-based strategy, the class assigned is +1, because the density in C1 is node, and (ii) the label assigned is the one with highest frequency in the neighborhood. In the example of Figure 6 (a), the method based on k-hop neighborhoods with k = 3 labels node A with class +1, because the frequencies in its three-hop neighborhood are [