Esther Galbrun
email: esther.galbrun@inria.fr

Pauli Miettinen
email: pauli.miettinen@mpi-inf.mpg.de

Analysing Political Opinions Using Redescription Mining

Understanding the socio-economical background of voters supporting a certain cause or, vice versa, understanding the political stance of people from a certain socio-economical niche are important questions in political sciences. Traditionally, answering these questions has required the researcher to fix either the political stance or the socio-economical background. In this paper, we propose using redescription mining to automatically find the stances and niches that correspond to each other. We show how redescription mining can be applied to open data from voting advice applications, providing insights about the position of the candidates to parliamentary elections. Furthermore, we show that these insights are not only descriptive, but that they also generalize well to new data.

I. INTRODUCTION

Are people from low-income classes more likely to support tax reductions? Is there any feature common to people supporting high levels of development aid? These and similar questions are traditionally answered via opinion polls. Conducting polls is expensive, however, and the polls are usually designed to answer at most a handful of questions. Today we have much more data about people's opinions than any single poll could collect, and utilizing this data is the key to understanding the current political opinions and trends. Such data typically does not constitute an unbiased sample, is noisy, and has many other issues, but these issues are often alleviated by the volume of the data. A more important problem, if less often mentioned, is that we do not know what questions to ask.

We know how to answer, say, the example questions above. But what if we cannot identify the polarizing topics a priori? What if we do not know which socio-economical niches are the interesting ones? In this paper, we propose to use redescription mining to address that issue. Broadly speaking, a redescription consists of two ways to describe the same set of entities. For example, characterizing a set of people based on their socioeconomical status on one hand and characterizing roughly the same set of people based on their political opinions, on the other hand, would constitute a redescription. The goal of redescription mining is to automatically find good redescriptions, that is, redescriptions that are both accurate and cover large-enough portions of the data.

We use data from two Finnish voting advice applications. The data contains background information about the candidates to the Finnish parliamentary elections in 2011 and 2015, as well as their answers to a number of policy questions. The candidates to parliamentary elections are hardly a good sample of the general population; however, our purpose is not to study the opinions of the general Finnish population, but to demonstrate the usability of redescription mining in this kind of political analysis.

In the following, we will first briefly present redescription mining in more formal terms (Section II), before giving a short introduction to Finnish politics (Section III-A), and explaining the data (Section III-B). In Section IV, we present an analysis of our results from the data. Again, our main purpose is to show the applicability of redescription mining to political data analysis, though we do also make interesting observations regarding Finnish politics.

II. REDESCRIPTION MINING

Redescription mining is a descriptive data analysis task which aims at simultaneously finding multiple descriptions of a previously unspecified subset of entities [START_REF] Ramakrishnan | Turning CARTwheels: An alternating algorithm for mining redescriptions[END_REF]. This is in contrast with other methods like emerging pattern mining, contrast set mining, or subgroup discovery (see [START_REF] Novak | Supervised descriptive rule discovery: A unifying survey of contrast set, emerging pattern and subgroup mining[END_REF] for a unifying survey) and with general classification methods, where target subsets of entities are specified via labels.

We consider data that contain entities with two sets of characterizing variables. For instance, in the setting considered here, the entities might be candidates to a political election with variables characterizing their personal profile (age, gender, profession, party affiliation, etc.) on one hand, and their position on a selection of issues (pension indexation, membership in NATO, developing wind power, etc.). Then, the goal of redescription mining is to find a pair of queries, one query for each set of variables, such that both queries describe (almost) the same set of entities. We refer to the two sets of variables as left and right hand side data, and the queries over them, respectively, as left and right hand side queries.

More formally, variables can be either Boolean, categorical, or numerical. Boolean variables can be interpreted as a truth value assignment in a natural way. For categorical and realvalued variables, truth value assignments are induced by relations

[v = c] and [a ≤ v ≤ b],
respectively, where c is some category and [a, b] an interval. These truth assignments and their negations constitute literals which can be combined using the Boolean operators ∧ (and) and ∨ (or) to form queries.

Then, a redescription is simply a pair of queries over variables from the two sets. The support (supp) of a query is the subset of entities for which the query holds true. The accuracy of a redescription is measured by the Jaccard coefficient (J) of the supports of its two queries; p-values indicating how likely it is to observe such an overlap for independent queries can be used to reject uninteresting redescriptions.

Several algorithms for redescription mining have been proposed over the years, based in particular on mining and pairing itemsets [START_REF] Galbrun | From Black and White to Full Colour: Extending Redescription Mining Outside the Boolean World[END_REF], on learning classification trees [START_REF] Ramakrishnan | Turning CARTwheels: An alternating algorithm for mining redescriptions[END_REF], [START_REF] Zinchenko | Mining predictive redescriptions with trees[END_REF] or on building queries greedily [START_REF] Galbrun | From Black and White to Full Colour: Extending Redescription Mining Outside the Boolean World[END_REF]. The redescriptions presented in this paper were obtained with tree based algorithms [START_REF] Zinchenko | Mining predictive redescriptions with trees[END_REF] and with the REREMI algorithm [START_REF] Galbrun | From Black and White to Full Colour: Extending Redescription Mining Outside the Boolean World[END_REF], since these algorithms are able to handle numerical and categorical data as well as missing values, as found in the datasets of interest here. Tree based algorithms build queries by learning classification and regression trees (CART) over either sets of variables in turn while alternating between the two sides, at each step trying to best match the labels assigned by the tree obtained at the previous one. REREMI, on the other hand, is a greedy algorithm that mines redescriptions by iteratively appending new literals to the current queries, at each step keeping the best candidates for further extension. The analysis was carried out using SIREN, 1 an interface that allows to interactively mine, visualize and edit redescriptions [START_REF] Galbrun | Siren: An interactive tool for mining and visualizing geospatial redescriptions[END_REF].

III. THE DATA

A. Introduction to Finnish Politics

The constitution of Finland [START_REF]Constitution of Finland[END_REF] declares Finland to be a parliamentary representative democratic republic. The unicameral Parliament of Finland has 200 members and the electoral period is four years [START_REF]Constitution of Finland[END_REF]. Finland has a multi-party system and typically no party holds the majority of the votes. 2 The 2015 parliament, for example, has representatives of eight different parties. 3 As a consequence, the government is usually formed as a coalition of multiple parties, and even the grand coalitions between socialistic and non-socialistic parties are common. The current cabinet (since the 2015 elections) has ministers from three parties, while the cabinet that started after the 2011 elections had ministers from six parties.

The members of parliament are elected every four years on a direct election. For the purpose of the elections, Finland is divided into electoral districts, and the number of seats assigned to each district is proportional to the population. In the 2011 parliamentary elections, there were 14 districts in the mainland but this was reduced to 12 in the 2015 elections. The electoral districts are shown in Figure 1.

Within each electoral district, the seats are allocated following D'Hondt's method [START_REF] Gallagher | Proportionality, disproportionality and electoral systems[END_REF]: The votes given for all candidates of a party are summed up and the candidates within the party are ordered based on the number of votes they received. They are then assigned a comparison number that is the total number of votes the party received divided by the candidate's position within the party. The seats of the electoral district are assigned to the candidates who obtained the highest comparison numbers.

The Finnish election system is thus a complete open list: the order of the candidates within the parties' lists are determined solely based on the votes received by the candidates and there are no official thresholds on the minimum number of votes a candidate needs to receive so as to gain a seat. This means that during the campaign, the candidates try to accomplish two tasks: on one hand, they need to earn as many votes to their party as possible, but on the other hand, they need to earn more votes than the other candidates of their party in order to rank higher on the list. Thus, while the candidates generally follow the platform of their party, they might disagree on some topics or have different priorities in order to distinguish themselves from the other candidates of the party.

In the 2011 and 2015 elections, eight parties won seats in the parliament. The (Finnish) abbreviations used for those parties, their English names, and the number of MPs they had in 2011 and 2015 are shown in Table I. The parties are ordered, from top to bottom, following their seating in the parliament, from left to right, as seen by the Speaker.

B. The Data Sets

For our analysis, we use data from two different Finnish voting advice applications (VAA), one from 2011 and one from 2015. VAAs are online services that collect candidates' answers to various policy questions and allow users to find the candidates whose answers are most closely aligned with theirs. Our data contain background information about the candidates (age, party, region, education level, income level, previous political positions, etc.) and their answers to a series of questions. For this work, we considered only the 675 candidates who ran for both the 2011 and the 2015 elections. The distribution of candidates per region is shown in Figure 1, and per party in Figure 2.

The questions in the HS11 data 4 are from the VAA ran by Helsingin Sanomat (HS) daily newspaper for the 2011 elections, while the questions in the Yle15 data5 [START_REF]Yle julkaisee vaalikoneen vastaukset avoimena datana[END_REF] are from the VAA ran by the Finnish Broadcasting Company Yle for the 2015 elections. The HS11 data contains 29 yesno questions and 2 multiple-choice questions; in addition, the candidates could mark questions which they consider particularly important. The Yle15 data has 86 questions on a 5-point answer scale (disagrees completely-disagrees-neutralagrees-agrees completely) and 11 yes-no questions.

In addition, we merged the questions of HS11 and Yle15 to form the HS11 Yle15 data. That is, in HS11 Yle15 we have the answers the candidates gave to the HS11 questions on the left-hand side and their answers to the Yle15 questions on the right-hand side. Queries over the answers in the HS11 data and in the Yle15 data are denoted as Q11 and Q15 respectively while queries over the profile information are respectively denoted as P11 and P15. Thus, a redescription

IV. ANALYSIS OF THE RESULTS

For the analysis, we used the SIREN software for redescription mining. For all results, we used the REREMI algorithm; for the policy questions, we allowed only conjunctions over the questions; over the profiles, we allowed arbitrary queries. The data and our full results are freely available. 6In the following, we will first present an analysis of some example results from the three data sets. We tested the statistical significance of the redescriptions we found against the null hypothesis that the results are due to a random distribution of the answers following the approach explained in [START_REF] Galbrun | From Black and White to Full Colour: Extending Redescription Mining Outside the Boolean World[END_REF]; all of the redescriptions we found were significant at the significance level of 0.01.

The main purpose of these analyses is to demonstrate what kind of insights we can gain by using redescription mining, confirming the usability of redescription mining for the task of political data analysis. We will also use different visualizations of the redescriptions to better interpret them.

A. The 2011 Elections

We present four redescriptions from the HS11 data in Table II. 7 The first redescription has a very high Jaccard coefficient, at 0.833, and relatively high support, of 448 candidates. It says that the candidates who are between 24 and 58 years old, have a university degree, or hold an elected position at the regional level are those who want to limit the municipalities to no more than 290, and do not want three niche parties (Köyhien Asialla (KA), Piraattipuolue (PIR), Suomen Senioripuolue (SEN)) in the government. Overall, this redescription covers most of the mainline politicians.

Figure 3(a) shows a decision forest corresponding to this redescription. From it, we can see that the candidates who agree with the questions but do not fit the profile (blue lines) are distributed rather evenly over the part of the profile they do not fit. On the other hand, the candidates who do fit to the profile, but do not agree with the questions (red lines), mostly disagree with the number of municipalities.

The second redescription concerns the question of whether the parliament should grant permission to build a new nuclear power plant. Here, the question part selects the candidates who are against the power plant, while the profile identifies candidates who are either between 51 and 58 years old, have a university degree, or were not members of the parliament at the time of answering. Despite the very inclusive profile, the redescription still has rather high Jaccard coefficient, at 0.656.

It is interesting to focus on the profiles of those candidates who are against the power plant but do not fit the profile of the redescription. Looking at the blue lines in Figure 3(b), we notice that most of them have a relatively high education level, and most are also above the selected age range.

The third redescription selects candidates who are either female or have lower education levels and who disagree with all the proposed methods for extending work careers, such as increasing the retirement age or removing the option of going on part time retirement. These candidates, in other words, are probably against extending work careers in general. That the concept of extending work careers is less popular among the candidates with lower education (mostly workingclass candidates) is not surprising. That female candidates, irrespective of their education, are also against extending work careers is more surprising.

The final redescription in Table II selects the candidates from the Green League. This redescription support consists of 46 candidates out of the 59 Green League candidates. This redescription mostly follows the party platform for the Green League: the party is against the new nuclear power plant, thinks Finland should help Greece deal with the debt crisis, wants to keep the level of development aid stable, and -unsurprisingly -would like to see the Green League in the cabinet. It is perhaps interesting to note that we did not find any other redescription identifying other major parties than the one presented here. This shows the diversity of opinions among the parties' candidates caused by the Finnish election system, as explained in Section III-A.

B. The 2015 Elections

The first redescription in Table III again has a very high Jaccard coefficient, at 0.877. Similarly to the first redescription from the HS11 data, it also describes rather mainline candidates: their election budget is above 1,000 euros, their annual income above 30,000 euros, or they have either no prior political experience or have political experience at the regional level. On the question side, they do not strongly disagree with the request for more funding for the police nor with the claim that Russia is a potential threat to Finland, and do not strongly agree that GMO food is safe.

The second redescription has a simple query over the questions: it selects those candidates who do not strongly agree with having no limits on the opening hours of businesses. The profile, on the other hand, is more complex: it selects only candidates who have a campaign budget lower than 20,000 euros, and among those, the ones who are either from the Communist Party (SKP), are between 47 and 74 years old, or have been elected to a municipal council.

The third redescription again concerns an important policy question in Finland: whether the citizens' right for free, highquality health care -an important part of the Finnish welfare society -should be enforced by the government, even if that violates the autonomy of the municipalities -an important feature of the Finnish political system. The exact redescription selects the candidates who are between 34 and 74 years old or have experience in regional-level politics and do not strongly disagree with the claim that security is more important than privacy on the Internet (an opinion that is widely shared among candidates in the Yle15 data), and agree that the citizens' right for healthcare is more important than the municipal autonomy.

The final redescription identifies candidates who do not completely agree with allowing euthanasia. Namely, they are the candidates who are either over 37 years old or have children.

C. Joint Data

The HS11 Yle15 data is very different from the previous two data sets. We do not anymore identify candidates based on their profiles and political opinions, but instead based on their answers to questions in 2011 and 2015. This is particularly enlightening, as the questions are sent out by two different media institutions and have a somewhat different emphasis.

The first two redescriptions in Table IV have only one variable on both sides, and they cover popular policy questions. The first redescription selects the candidates who, in 2011, did not think that immigration laws are too strict and in 2015 did not strongly agree that Finland should take more responsibility on immigrants arriving to the EU. That is, these are the candidates who are, if not hostile to immigration, at least reserved towards increasing the number of immigrants. The second redescription selects the candidates who did not want to cut the public spending by reducing the development aid in 2011, and in 2015 did not strongly agree that immigration should be limited because of terrorism threats. These are, in other words, the II.

(c) Decision forest corresponding to the last redescription in Table IV.

Figure 3. Illustrations of some of the redescriptions. The purple lines correspond to the candidates who agree with both queries (P11 and Q11 in HS11 or Q11 and Q15 in HS11 Yle15), the red lines are candidates who agree with the left-hand query (P11 in HS11, Q11 in HS11 Yle15), but not the right-hand query, while the blue lines are the candidates who agree with the right-hand query (Q11 in HS11 and Q15 in HS11 Yle15) but not with the left-hand query. opposite of the above candidates, though many moderates probably fit both of these redescriptions.

The third redescription shows an interesting pattern. In early 2015, the President of Finland signed a new gender-neutral marriage act. Some candidates in the 2015 elections, unhappy that the act passed, proposed to cancel the act. The third redescription shows that the candidates who, in 2015, did not want to cancel the act, are also those who earlier in 2011 did not want to reduce the development aid, did not want Christian Democrats in the government, and did not choose Israel as a country that should be Finland's Facebook friend, if countries would have Facebook accounts. Supporting the gender-neutral marriage act and development aid can be considered as standard liberal political opinions, while the Christian Democrats are typically seen as a rather conservative party, especially when it comes to topics such as marriage.

The fourth redescription concerns a recurring topic in Finnish politics: whether Finland should join the NATO. The redescription selects those candidates who in 2015 strongly disagreed with the claim that joining NATO is good for Finland and who in 2011 did not want to join NATO, did not want to increase the amount of outsourcing the municipalities do, and did not want the Swedish People's Party to participate in the government. The last two opinions are typical of left-

Dataset

# red. J ratio J overall p-V overall HS11 62.80 ± 2.52 0.93 ± 0.19 0.58 ± 0.14 0.00 ± 0.00 Yle15 54.70 ± 3.32 0.93 ± 0.15 0.66 ± 0.14 0.00 ± 0.00 HS11 Yle15 48.80 ± 4.33 0.95 ± 0.11 0.73 ± 0.05 0.00 ± 0.00 wing politicians, although the attitude towards the NATO does not follow the left-right division so clearly. Nonetheless, it is clear from this redescription that the candidates who are against Finland being a member of NATO also have some left-wing policy opinions. The decision forest corresponding to this redescription is presented in Figure 3(c). From it, we see that most of the candidates who in 2015 strongly disagree with the claim that joining the NATO is good for Finland, but did not agree with the claims in 2011 (i.e. the blue lines in Figure 3(c)), would have accepted the Swedish People's Party into the government.

D. Generalization Experiments

So far, we have interpreted our results as descriptive patterns, that is, they tell us something about the data as it is. In this section, we test whether our results are also predictive, that is, whether they generalize to the opinions of candidates not included in the data. To that end, we performed a test similar to 10-fold cross-validation: we divided the data randomly into 10 equally-sized parts and ran 10 tests. In each test, we held out one part and mined the redescriptions from the training data consisting of the 9 remaining parts. We then computed the Jaccard coefficients of these redescriptions over the testing data, that is, the hold-out part. If the redescriptions have approximately the same Jaccard coefficient in both training and testing data, they are considered to generalize well. For further details about the process, see [START_REF] Zinchenko | Mining predictive redescriptions with trees[END_REF].

The results of the generalization experiments are reported in Table V. They show that in our 10-fold experiment, the redescriptions had very constant quality in both the training and testing data (the ratio of the Jaccard coefficients is almost 1) with relatively high overall Jaccard coefficient. Overall, these results confirm that the redescriptions do not only describe the data, but can also generalize to candidates not covered by the data.

V. RELATED WORK

Voting Advice Applications (VAA) are systems that provide support to citizens in making their voting decision by comparing their position on various political issues to the positions of candidates, whether individual politicians or political parties [START_REF] Marschall | Voting advice applications in a comparative perspective: an introduction. Matching Voters with Parties and Candidates[END_REF]. The VAAs are often based on asking the users about their opinion on a number of policy statements, and comparing their answers to the positions of the candidates. Beside a list of candidates ranked by proximity, the VAA might display a low dimensional representation of the space of political opinions, for instance as a 2D projection or as radar plots, in which the candidates as well as the users can be placed and compared. The position of the candidates can be obtained externally through expert surveys or manifesto coding -a technique for "normalizing" political programs to allow comparison across time, between parties or between countries. Alternatively, it can be obtained through self-positioning, by having the candidates directly indicate their position regarding the selected statements.

A number of issues pertaining to the construction of VAAs have been pointed out and discussed, such as the selection and wording of the statements, the choice of evaluation, involving both agreement and importance ratings on a fixed scale for instance, the design of the matching algorithm [START_REF] Mendez | What's behind a matching algorithm: A critical assessment of how vaas produce voting recommendations[END_REF] and the choice of the projection space [START_REF] Germann | Spatial maps in voting advice applications: The case for dynamic scale validation[END_REF], with proposed improvements and alternatives (e.g. [START_REF] Korthals | Multi-attribute compositional voting advice applications (macvaas): a methodology for educating and assisting voters and eliciting their preferences[END_REF])

Currently, the number of voting advice applications available online is fairly high, covering a large number of countries and used by millions of users. The Dutch StemWijzer [START_REF] Graaf | The irresistible rise of stemwijzer. Voting Advice Applications in Europe: The State of the Art[END_REF], created in 1989, is the first known VAA. Finland was the first country to have such a system accessible online, in 1996 [START_REF] Ruusuvirta | Much ado about nothing? Online voting advice applications in Finland. Voting advice applications in Europe. The state of the art[END_REF].

The impact of VAAs on voters' behaviour is also a subject to much debate [START_REF] Hanel | Analyzing the political communication patterns of voting advice application users[END_REF], [START_REF] Vassil | Voting Smarter? The impact of voting advice applications on political behavior[END_REF], with multiple studies aiming to analyse the effect of these systems on voters' loyalty to political parties [START_REF] Enyedi | The influence of voting advice applications on preferences, loyalties and turnout: An experimental study[END_REF], for instance, or evaluate their perceived usefulness [START_REF] Alvarez | Voting advice applications: How useful and for whom?[END_REF]. Mendez et al. [START_REF] Mendez | Methodological challenges in the analysis of voting advice application generated data[END_REF] take a rather practical data analysis point of view on the problem of processing data generated by VAAs to reach sociological conclusions. We note, however, that our approach is different from the approaches considered in these papers, as we do not study the users, but the candidates, and we do not aim at drawing conclusions, e.g., regarding the voting results.

In [START_REF] Grosskreutz | Subgroup Discovery for Election Analysis: A Case Study in Descriptive Data Mining[END_REF], Grosskreutz et al. employed a data mining method related to the one used here. They applied subgroup discovery to identify relations between socio-economic variables and elections results at the level of voting districts in the german city of Cologne.

VI. CONCLUSIONS

In this paper, we have demonstrated the usability of redescription mining for political data analysis. In particular, we have shown how redescription mining can be applied to data from voting advice applications. VAA data, however, is only an example, and we argue that the same methods can be applied to any data with two disjoint sets of variables. In particular, redescription mining can be used with any opinion poll data that records both socio-economical information about the individuals as well as their opinions. Verifying that redescription mining indeed works with other types of data as well is an important topic for future research.

Figure 1 .

 1 Figure 1. Electoral districts of Finland in 2011 (left) and 2015 (right) parliamentary elections. The numbers xx/yy(zz) below the name show the number of seats (xx), the total number of candidates (yy), and the number of candidates in our data (zz).

  P11: [Gender = F] ∨ [1 ≤ EduLvl ≤ 5] 0.655 364 Q11: [Q7.ExtWCareer = NotAny] P11: [Party = Vihr] 0.639 46 Q11: ¬Q3.NuclearPow ∧ [Q10.GreekDebt = FinInterest] ∧[Q20.DvlAid = Keep] ∧ Q31.GvtPrt.Vihr from HS11 consists of a pair of queries P11 and Q11, while a redescription from HS11 Yle15 consists of a pair of queries Q11 and Q15.

  (a) Decision forest for the first redescription in Table II. (b) Parallel coordinates plot for the second redescription in Table

  RedescriptionJ supp Q11: [Q25:Immigration = TooStrict] 0.867 442 Q15: [Q150.more.responsib.EU.immigrants ≤ 1] Q11: [Q9:CutPblExpend = RedDvlAid] 0.848 442 Q15: [Q139.limit.immigrat.bc.terrorism ≤ 1] Q11: [Q20:DvlAid = Reduce] ∧ ¬Q21:Fb:Israel 0.803 347 ∧¬Q31:GvtPrt:KD Q15: ¬Q246.cancel.gender.neutral.marriage.law Q11: [Q17:NATO = YesNotSoon] ∧ ¬Q31:GvtPrt:RKP 0.776 368 ∧[Q27:MunOutsource = IncButChoose] Q15: [Q137.NATO.is.good ≤ -1]

Table I PARTIES

 I IN THE FINNISH PARLIAMENT. NUMBER OF MPS IS BASED ON THE SITUATION RIGHT AFTER THE ELECTION. THE PARTIES THAT FORMED THE CABINET AFTER THE ELECTION ARE HIGHLIGHTED IN BOLDFACE.

							Number of MPs
	Abbrev. English name			2011		2015
	Vas	Left Alliance			14		12
	SDP	Social Democratic Party		42		34
	Vihr	Green League			10		15
	PS	Finns Party			39		38
	Kesk	Centre Party			35		49
	KD	Christian Democrats		6		5
	Kok	National Coalition Party		44		37
	RKP	Swedish People's Party a		10		10
	a Includes Åland's MP in 2011 and 2015.
	69	100	59	85	79	59	77	22	125
	2011								/675
	Vas	SDP	Vihr	PS	Kesk	KD	Kok	RKP	others
	2015								/675
	68	96	61	81	83	55	75	24	132

Figure 2. Number of candidates in our data per party in 2011 (HS11 data)

and 2015 (Yle15 data) elections. We show the parties that won a seat in the parliament in either of the elections (excluding the representative from Åland); the total number of candidates by the other parties is reported under "others."

Table II SAMPLE

 II REDESCRIPTIONS FROM THE HS11 DATA SET.

	Redescription	J supp
	P11: [24 ≤ Age ≤ 58] ∨ [7 ≤ EduLvl] ∨ RegElected	0.833 448
	Q11: [Q28.MunNb ≤ 290] ∧ ¬Q31.GvtPrt.KA
	∧¬Q31.GvtPrt.PIR ∧ ¬Q31.GvtPrt.SEN
	P11: [51 ≤ Age ≤ 58] ∨ [7 ≤ EduLvl] ∨ ¬MP	0.656 366
	Q11: ¬Q3.NuclearPow

Table III SAMPLE

 III REDESCRIPTIONS FROM THE YLE15 DATA SET.

	Redescription	J supp
	P15: [1000 ≤ budged.EUR] ∨ [30000 ≤ income.EUR]	0.877 449
	∨pol.exp.none ∨ pol.exp.regional.level
	Q15: [-1 ≤ Q138.more.police] ∧ [-1 ≤ Q140.Russia.is.threat]
	∧[Q149.GMO.is.safe ≤ 1]
	P15: ([party = SKP] ∨ [47 ≤ age ≤ 74]	0.783 418
	∨pol.exp.municip.council) ∧ [budget.EUR ≤ 20000]
	Q15: [Q128.no.limit.opening.hours ≤ 1]
	P15: [34 ≤ age ≤ 74] ∨ pol.exp.regional.level	0.775 403
	Q15: [-1 ≤ Q141.security.more.import.privacy.in.net]
	∧[1 ≤ Q147.right.for.healthcare.over.munic.autonomy]
	P15: [37 ≤ age] ∨ children	0.745 388
	Q15: [Q143.allow.euthanasia ≤ 1]

Table IV SAMPLE

 IV REDESCRIPTIONS FROM THE HS11 YLE15 DATA SET.

Table V GENERALIZATION

 V TEST: MINING REDESCRIPTION IN 10-FOLDS. WE REPORT THE NUMBER OF REDESCRIPTIONS MINED (#), THE AVERAGE OF THE RATIO BETWEEN THE ACCURACY (JACCARD COEFFICIENT, J) IN THE TRAINING SET AND THE HOLD-OUT SET, THE AVERAGE ACCURACY OVERALL AND AVERAGE p-VALUE OVERALL (± STANDARD DEVIATION).

http://siren.gforge.inria.fr/main/

So far it has only happened once that a single party held the majority.

In addition, the constitution[START_REF]Constitution of Finland[END_REF] assigns one seat to the representative of Åland; this representative is usually not from any of the mainland parties, but works together with the Swedish People's Party of Finland.

http://blogit.hs.fi/hsnext/hsn-vaalikone-on-nyt-avointa-tietoa, licensed as Creative Commons BY-NC-SA 3.0.

https://www.avoindata.fi/data/fi/dataset/eduskuntavaalien-2015-ylenvaalikoneen-vastaukset-ja-ehdokkaiden-taustatiedot, licensed as Creative Commons BY 4.0

http://people.mpi-inf.mpg.de/~pmiettin/pol_redesc/

The variables in these tables are in abbreviated format, as in the data. The full questions and answers are available in the meta-data of the data sets.


Esther Galbrun
email: esther.galbrun@inria.fr

Behzad Golshan
email: behzad@recruit.ai

Aristides Gionis
email: aristides.gionis@aalto.fi

Evimaria Terzi
email: evimaria@cs.bu.edu

Finding low-tension communities

Motivated by applications that arise in online social media and collaboration networks, there has been a lot of work on community-search. In this class of problems, the goal is to find a subgraph that satisfies a certain connectivity requirement and contains a given collection of seed nodes.

In this paper, we extend the community-search problem by associating each individual with a profile. The profile is a numeric score that quantifies the position of an individual with respect to a topic. We adopt a model where each individual starts with a latent profile and arrives to a conformed profile through a dynamic conformation process, which takes into account the individual's social interaction and the tendency to conform with one's social environment. In this framework, social tension arises from the differences between the conformed profiles of neighboring individuals as well as from the differences between individuals' conformed and latent profiles.

Given a network of individuals, their latent profiles and this conformation process, we extend the communitysearch problem by requiring the output subgraphs to have low social tension. From the technical point of view, we study the complexity of this problem and propose algorithms for solving it effectively. Our experimental evaluation in a number of social networks reveals the efficacy and efficiency of our methods.

Introduction

A large body of work in social and collaboration networks focuses on solving variants of the communitysearch problem [START_REF] Faloutsos | Fast discovery of connection subgraphs[END_REF][START_REF] Ruchansky | The Minimum Wiener Connector Problem[END_REF][START_REF] Sozio | The community-search problem and how to plan a successful cocktail party[END_REF][START_REF] Tong | Center-piece subgraphs: Problem definition and fast solutions[END_REF], where the high-level goal is to find a subgraph that connects a set of seed nodes and satisfies certain connectivity properties. This problem has applications primarily in online social media and collaboration networks. For example, solutions can be used to identify a set of individuals who are the most appropriate group to organize a social gathering.

Different variants of the problem impose different requirements on the structure of the solution subgraph. For example, in some settings one asks to find highdensity communities [START_REF] Sozio | The community-search problem and how to plan a successful cocktail party[END_REF], while in others the objective is to find small-diameter communities [START_REF] Ruchansky | The Minimum Wiener Connector Problem[END_REF].

In contrast to the static requirements imposed by existing work, in this paper we incorporate the dynamics of social interactions in the community-search problem. We do so by associating profiles to the individuals in the network. The profiles of individuals model their interests, skills, preferences, opinions, and so on, with respect to different aspects or topics. For example, the profile may represent the interest of an individual in discussing about politics, or the working style of an individual -e.g. whether he is a morning person or a night owl. Since profiles may cover a number of different aspects or topics, we assume that they are represented as multi-dimensional vectors.

We further assume that the profiles of individuals change due to the social influence they receive from other individuals in the network. We model this change through what we call conformation process, which is a dynamic process. Motivated by existing work on models of opinion formation and social influence [START_REF] Clifford | A Model for Spatial Conflict[END_REF][START_REF] Degroot | Reaching a Consensus[END_REF][START_REF] Friedkin | Social influence and opinions[END_REF][START_REF] Holley | Ergodic Theorems for Weakly Interacting Infinite Systems and the Voter Model[END_REF][START_REF] Friedkin | Social influence networks and opinion change[END_REF] we assume that the conformation process is a repeated-averaging process. In our work, we generalize this process from one-dimensional opinions to multidimensional profiles. The effect of this process is that the initial profiles of individuals, which we call latent profiles, get re-enforced or altered through synthesis and aggregation of different viewpoints of the network participants. Hence, the conformed profiles are formed through a process of repeated averaging.

Given this process, the latent profiles of individuals and a social network that represents their social interaction, social tension arises because of the differences between the conformed profiles of neighboring nodes and between the conformed and latent profiles of the nodes themselves. In this context, our goal is to identify communities that are not only connected, but also exhibit low social tension. We refer to this problems as the T -Comm problem. To the best of our knowledge we are the first to define and study this problem in the light of profile-conformation processes in a social network.

In terms of technical results, we show that the T -Comm problem is NP-hard and we design graphtheoretic algorithms for solving it. A key difficulty that we overcome while designing these algorithms is that we do not run the conformation process for every step of these algorithms; indeed, this would be computationally very demanding. Rather, we create effective proxies of this process that allow our algorithm to scale. Our experiments with real-world data demonstrate the efficiency and the efficacy of our algorithms.

While we focus here primarily on a communitysearch problem, we also considered a team-formation variant, where the goal is to find individuals who collectively have the skills required for a task and form a connected subgraph with some required properties. 11.1 Applications. The T -Comm problem has numerous potential applications. For example, when analyzing social networks or social media, it is often useful to identify connected groups of users who have similar profiles with respect to a topic or an idea (i.e. they are in agreement). Note, however, that minimizing the social tension does not necessarily imply looking for highly homogeneous communities but, rather, favoring communities that are able to bridge opinion gaps at low social and communication costs. Groups with low social tension can be recommended as ideal in order to form a group to organize or to invite at a social event. Such problems also arise in human-resource management, when searching for groups of workers who can collaborate together in a conflict-free manner in order to successfully complete a project. Being able to identify a group of people who are not going to experience high social tension is particularly useful when considering cluster hires in universities or start-up companies, where the investment is high and the human factor risk needs to be minimized.

Related Work

To the best of our knowledge, we are the first to combine the problem of identifying a group of nodes from an input graph with an underlying dynamic conformation process. However, while the T -Comm problem as we define it is novel, our work is related to existing work on graph mining and opinion dynamics. We summarize the related literature below.

2.1 Community search. Given a graph and a subset of its nodes as a seed, community-search problems ask for a set of nodes which is a superset of the seed nodes and induces a connected subgraph in the original graph. Since this class of problems was initially introduced [START_REF] Faloutsos | Fast discovery of connection subgraphs[END_REF][START_REF] Tong | Center-piece subgraphs: Problem definition and fast solutions[END_REF], different instances of the communitysearch problem appeared. Each one imposes a different requirement on the graph-theoretic properties of the reported subgraph, e.g. maximizing the density [START_REF] Sozio | The community-search problem and how to plan a successful cocktail party[END_REF] or minimizing the average pairwise distance [START_REF] Ruchansky | The Minimum Wiener Connector Problem[END_REF]. Although these problems are related to the T -Comm problem we study here, the novelty of our problem comes from the fact that we associate nodes with profiles and that we assume a profile-conformation process that takes place over the network. Our objective function is directly related to this process as it aims to minimize the social tension in the reported community. As a result, the technical results we obtain for T -Comm are different from the other community-search problems.

2.2 Opinion dynamics. Starting in the 1970s, models have been built that try to capture the opinionformation processes in groups and networks [START_REF] Clifford | A Model for Spatial Conflict[END_REF][START_REF] Degroot | Reaching a Consensus[END_REF][START_REF] Friedkin | Social influence and opinions[END_REF][START_REF] Holley | Ergodic Theorems for Weakly Interacting Infinite Systems and the Voter Model[END_REF][START_REF] Yildiz | Binary Opinion Dynamics with Stubborn Agents[END_REF][START_REF] Friedkin | Social influence networks and opinion change[END_REF]. For example, voter models, pioneered by Clifford and Sudbury [START_REF] Clifford | A Model for Spatial Conflict[END_REF] and Holley and Liggett [START_REF] Holley | Ergodic Theorems for Weakly Interacting Infinite Systems and the Voter Model[END_REF] are stochastic models of opinion formation where at each step a node is selected at random and adopts the opinion of one of its neighbors, also selected at random. In DeGroot's averaging model [START_REF] Degroot | Reaching a Consensus[END_REF], each node updates its opinion, by the weighted average of its own opinion and its neighbors' opinion at the previous time step. Friedkin and Johnsen [START_REF] Friedkin | Social influence and opinions[END_REF][START_REF] Friedkin | Social influence networks and opinion change[END_REF] introduced a model where every node has an immutable inner opinion and a changeable expressed opinion. Each node forms its expressed opinion in a repeated-averaging process involving its own inner opinion and the expressed opinions of its neighbors. Given the popularity of this model we also adopt it for modeling our profile-conformation process, and extend it to multiple dimensions.

The Friedkin and Johnsen model has been used in recent works by Bindel et al. [START_REF] Bindel | How Bad is Forming Your Own Opinion?[END_REF] and by Gionis et al. [START_REF] Gionis | Opinion Maximization in Social Networks[END_REF]. Bindel et al. focus on the price of anarchy in terms of the tension achieved through local repeated averaging and global opinion coordination. Gionis et al. aim at identifying the set of nodes whose opinions need to be changed so that the overall positive opinion in the network is maximized. Although our work builds upon Friedkin and Johnsen's ideas to model the profiles and their conformation process, none of the abovementioned works addresses the question of identifying a subgraph with low social tension as we do.

Preliminaries

Throughout the paper we consider a social network G = (V, E) where the nodes in V correspond to individuals and the edges in E represent the interactions between these individuals. For simplicity of exposition, we present the case of an unweighted and undirected graph, but the problem and algorithms we discuss can naturally be extended to weighted and directed graphs.

The set of neighbors of node i in G is denoted by N G (i). Given a subset of vertices U ⊆ V , we let E(U ) denote the set of edges of G induced by U , i.e. E(U ) = {(i, j) ∈ E, i, j ∈ U }, and G(U ) denote the corresponding induced subgraph G(U ) = (U, E(U )).

3.1 Profiles. Evidently, each individual has their own set of preferences (e.g. style, habits, biases, and opinions). We refer to this personal set of preferences as a profile. For now, let us assume that profiles only reflect preferences regarding a single aspect (e.g. working style), that is, profiles consist of a single attribute. We assume that profile attribute values are represented by a real number in the interval [0, 1] (e.g. a value between 0 and 1 may represent an individual's preference towards a certain software tool).

The key characteristic of our model is that it captures the interaction between the user profiles and their social connections. This is done by assuming that each individual i has a latent profile and a conformed profile, denoted by x i and f i respectively. The latent profile of an individual represents the individual's own true preference. However, individuals may choose not to act in accordance with their latent profiles as they try to minimize peer pressure by conforming their preferences to those of their peers. The conformed profile represents these adjusted preferences.

For simplicity, we first describe the model for singleattribute profiles, but later on we discuss how to extend it to multi-attribute profiles. We summarize the latent and conformed profiles of all n individuals with respect to a single attribute using vectors x and f respectively.

Measuring tension.

Due to the underlying social structures and mechanisms, the conformed profile f i of a node can differ from its latent profile x i . In such case, the node will bear an inner tension caused by the difference between its own latent and conformed profiles. On the other hand, the difference between the node's conformed profile and between the conformed profiles of its neighbors will cause cross tension. Hence, the total tension on node i is:

T i (G, x, f ) = (x i -f i ) 2 + j∈N G (i) (f i -f j ) 2 .
Then, the social tension of the network is simply the sum of the individual tensions, defined as

T (G, x, f ) = i∈V T i (G, x, f ) = i∈V (x i -f i ) 2 + j∈N G (i) (f i -f j ) 2 , (3.1)
which can alternatively be written as the sum of the overall inner and cross tensions

T (G, x, f ) = i∈V (x i -f i ) 2 + (i,j)∈E 2 (f i -f j ) 2 .

Conformation process.

But how do nodes arrive at their conformed profiles? Consider a repeated averaging process where at each step each node adjusts its conformed profile by setting it to the average of its latent profile and the conformed profile of its neighbors. Formally, denoting as f i (t) the conformed profile of node i at step t, we have:

(3.2) f i (t + 1) = x i + j∈N G (i) f j (t) 1 + |N G (i)| .
Computing the conformed profiles according to the repeated averaging model is equivalent to choosing f i to minimize T i (G, x, f ). That is, if each node aims to minimize its tension, the repeated averaging model provides an optimal choice for the conformed profiles. In that sense, using the repeated averaging model yields a Nash equilibrium for the tension, not a social optimum [START_REF] Bindel | How Bad is Forming Your Own Opinion?[END_REF].

A practical consideration is that in this model the latent profiles are assumed to be known, while the conformed profiles are the output of the conformation process. But, in practice, we have access to the conformed profiles while the latent profiles cannot be observed. This, however, does not constitute a problem for our model. One can swap the known and unknown variables of the system and solve for the latent profiles, given the conformed profiles and the original network.

The model adopted here for how conformed profiles emerge is a well-studied opinion-formation and socialinfluence model that has been introduced by sociologists [START_REF] Degroot | Reaching a Consensus[END_REF][START_REF] Friedkin | Social influence and opinions[END_REF][START_REF] Friedkin | Social influence networks and opinion change[END_REF]. In particular, the work of Friedkin et al. [START_REF] Friedkin | Social influence networks and opinion change[END_REF] validates this model by conducting a set of controlled experiments in which they observe how interactions between individuals in small groups influence their expressed opinions. The study demonstrates that the repeated-averaging model can both predict the opinions that individuals converge to, as well as the rate of convergence. Others have studied the mathematical properties of this model. For instance, it has been shown [START_REF] Bindel | How Bad is Forming Your Own Opinion?[END_REF][START_REF] Gionis | Opinion Maximization in Social Networks[END_REF] that the process converges in polynomial time to a fixed-point solution. In fact, the final conformed profiles can be computed by a matrix inversion [START_REF] Gionis | Opinion Maximization in Social Networks[END_REF], but actually repeating the averaging process leads to much faster computation.

Multi-attribute profiles.

Our assumption so far has been that profiles reflect the preferences of individuals with respect to a single attribute. But our notion of latent and conformed profiles can be easily extended to the case of multiple attributes, leading to multi-attributes -i.e. multi-dimensional -profiles. Assume there are m aspects or topics of interest, each associated to an attribute. The latent and conformed profiles can be simply extended from a single real number to real-valued vectors of dimensionality m, where each entry corresponds to one of the attributes. We summarize the latent and conformed profiles of n individuals on m attributes using n × m matrices X and F respectively. Note that each column of these matrices, denoted by x a and f a for a = 1, . . . , m, corresponds to a single attribute. In the multi-attribute case, the conformed profiles can be computed as before by applying Equation (3.2) in a column-wise fashion. Similarly, the social tension T (G, X, F) is defined as the sum of the social tensions across all m attributes.

The T -Comm problem

In this section, we introduce the T -Comm problem and study its complexity.

At a high level, the T -Comm problem aims to find a connected, low-tension community that involves a chosen subset of members. Formally, this intuitive statement is captured by the following problem definition:

Problem 1. (T -Comm) Given a network G = (V, E), latent profiles X and a set of seed nodes Q ⊆ V , find V ⊆ V such that Q ⊆ V , the graph G induced by V on G is connected and T (G , X, F) is minimized, where F is computed by the repeated averaging model on G .
Note that when defining the T -Comm problem, we assume that the social tension is computed as in Equation (3.1), X is the matrix containing the latent profiles of the nodes in V and F contains the conformed profiles of individuals, computed using the repeated averaging model described in the previous section (see Equation (3.2)) over the subgraph induced by V .

Given these assumptions, we can make the following observations with respect to the requirements imposed on the solution of T -Comm: as the number of edges in the resulting subgraph and the differences in the conformed profiles across these edges decrease, so does the social tension. In particular, the complete absence of edges results in no tension at all. However, the requirement that the output subgraph should be connected forbids such solutions.

From the application point of view, connectivity is important as it guarantees communication among the community members. One can see that minimizing tension and guaranteeing connectivity leads to an interesting trade-off between the density of edges and the homogeneity of the profiles of nodes in the reported subgraph. Communities should consist of individuals who share similar profiles or individuals who have divergent profiles but are needed to guarantee connectivity, these latter ones being preferably very sparsely connected with the rest of the community members. The exact cover by 3-sets problem, X3C for short, asks the following question. Given a universe of elements B = {b 1 , . . . , b p }, where the number of elements p is a multiple of 3, and a collection S = {s 1 , . . . , s q } of 3-elements subsets of B, is there a collection S ⊆ S such that every element in B occurs in exactly one member of S ?

Given an instance of the X3C problem, we construct an instance of the T -Comm problem with oneattribute profiles (i.e. m = 1) as follows. To each element b i in B we associate a node, called an "elementnode", with latent profile 0, and to each set s j in S we associate a node, called a "set-node", with latent profile 1. Each set-node is connected to the three nodes that represent the elements it contains. In addition, we make all the q set-nodes part of a larger clique D of o + q nodes with latent profiles equal to 1. Also, we make each element-node b i part of a larger clique A i containing o nodes with latent profiles 0. Finally, we assume that all the nodes in our construction are seed nodes except for the q set-nodes. This construction is illustrated in Figure 1.

We prove that if the given instance of X3C has an exact 3-set cover, then the minimum tension subgraph solution of T -Comm will contain the set-nodes of this exact cover.

The main idea of the proof is based on the following observation. Selecting a large (yet polynomial in p) value for o, increases the size of all cliques in our construction (i.e. clique D and all A i cliques). As a result, the conformed profile of all the nodes (including the set-nodes) in D will be very close to 1, and the conformed profiles of all nodes in the A i cliques will be very close to 0. Thus, the only non-negligible source of tension will be the tension across the edges that connect element-nodes to set-nodes. Each such edge would increase the tension by almost a unit.

Note that since each b i is a seed node, it has to be connected to the o seed nodes in D. This can be achieved only by going through a set-node. Thus, the solution to X3C has to pick a subset of set-nodes that cover all the element-nodes to ensure connectivity. Now, if x set-nodes are included in the subgraph then the tension would be roughly 3x. Obviously, the solution that minimizes the tension is the solution that picks the smallest number of set-nodes. This is achieved by selecting an exact cover, if such cover exists.

Algorithms for T -Comm

While the objective of the T -Comm problem is to minimize the social tension in the solution graph, T (G , X, F), obtaining the conformed profiles through the repeated-averaging process is costly; thus, it is not feasible to compute the social tension on a large number of candidate subgraphs. A possible alternative is to compute the conformed profiles by applying the repeated-averaging process on the whole graph once and use these profiles when evaluating the tension in the candidates later on. However, while designing our algorithms, we observed that this is a poor choice. Intuitively, the presence of a node with a latent profile that departs greatly from its neighbors' might significantly sway their conformed profiles. During the search, this node will likely be removed from the candidate set early on, but its effect would remain.

In order to avoid such effects, but also avoid the repeated computations of social tension we use the following trick in all our algorithms: for a pair of neighboring nodes i and j we assign to edge (i, j) ∈ E weight w ij = |x i -x j |. We then use this weight as a way of quantifying the contribution of this edge in the overall social tension. Although w ij is just a proxy of the edge's contribution, the trick appears to perform well in practice and leads to significant speedups. Once our algorithms obtain the set of nodes to report, we apply the repeated-averaging process on the induced subgraph in order to evaluate the social tension of the solution.

We propose two approaches for finding good candidate solutions for this problem.

5.1 Spanning-tree approach. This approach connects the seed nodes by building a spanning tree between them and is based on the 2-approximation algo-Input: Network G = (V, E), latent profiles X, seed nodes Q ⊆ V , path length function len() Output: Community nodes V 1: H ← complete weighted graph over nodeset Q, such that the weight of edge (i, j) is λ(i, j) = minp∈P ij len(p) with Pij the set of paths in G between i and j 2: K ← minimum spanning tree of H 3: V ← expand K by replacing edges by their corresponding shortest path in G 4: return V rithm for the Steiner tree problem [START_REF] Vazirani | Approximation Algorithms[END_REF]. It works as follows: first, it computes the shortest path between every pair of seed nodes. Next, it constructs a complete graph over the seed nodes such that the weight of the edge between two nodes corresponds to their shortest path distance in the original graph. Then, it considers the minimum-spanning tree from this complete graph, e.g. obtained with Prim's algorithm, and replaces each edge of the spanning tree with the associated original shortest path. The resulting subgraph constitutes the output of our tree-based algorithm. A sketch of this algorithm, called CTree, is shown in Figure 2. Note that this approach, searching for the best spanning tree, lacks any control over the induced edges that will be included in the solution. In this sense, it is an optimistic strategy.

We obtain different variants of this algorithm depending on the measure used to evaluate the length of a path. Having experimented with various options, we focus on two variants, where the length of the path is either (i) the number of edges involved, or (ii) the sum of weights of the edges along the path.

In other words, if p ij = (i, v 1 , v 2 , . . . , v k , j) is a path between i and j, we have len(p ij ) = k + 1 in the first variant, and len(p ij ) = w iv1 + w v1v2 + • • • + w v k j in the other. We denote these variants as CTree(e) and CTree(s) respectively.

The main step in our algorithm is the computation of the shortest path between all pairs of seed nodes by running the Dijkstra algorithm from each seed node in turn. The running time of our algorithm is thus

O(|Q| (|V | + |E| log |E|)).

Top-down approach.

The second algorithm is a top-down approach which starts with the full graph and iteratively removes nodes until it is no longer possible to continue without disconnecting the seed nodes. The pseudo-code for this algorithm, which we call CPeel, is given in Figure 3.

Again, we obtain different variants, this time by varying the score() function for choosing the next node to remove. We selected the following three scores:

Input: Network G = (V, E), latent profiles X, seed nodes Q ⊆ V , node scoring function score() Output: Community nodes V 1: V ← ∅; K ← V 2: while K = ∅ do 3: v ← arg max i∈K score(i, V ∪ K) 4: K ← K \ {v} 5: if Q is not disconnected in G(V ∪ K) then 6: K ← {i ∈ K, N G(V ∪K) (i) = ∅} 7: else 8: V ← V ∪ {v} 9: return V
(i) The score is a number assigned randomly to each node when initializing the algorithm, which determines the order in which the nodes are peeled. This random variant is denoted as CPeel(r). (ii) The score is the sum of the weights of the remaining edges adjacent to the node, i.e.

score(i, U ) = j∈N G(U ) (i) w ij .
(iii) The score is the largest weight among the remaining edges adjacent to the node, i.e.

score(i, U ) = max j∈N G(U ) (i) w ij .
The second and third scores are similar but the former uses sum where the latter takes the maximum, resulting in variants CPeel(s) and CPeel(m), respectively. Nodes with larger scores are considered first (line 3 in Figure 3). Meanwhile, in all three variants, nodes that get isolated are pruned away (line 6). Rather than favoring good connections, this second approach removes nodes that might generate large costs, and thus follows a pessimistic strategy.

In practice, we can find a minimum connecting tree using the strategy described previously. Then, when we are about to remove a node, we check whether it belongs to the current tree, in which case we need to look for an alternative tree that does not involve this node. Only if such a tree can be found can we safely remove the node. In the worst case, we would have to recompute the spanning tree for each node, resulting in a running time

O(|V | (|V | + |E| log |E|)).

Experiments

We now turn to the evaluation of the different variants of our proposed algorithms, CTree and CPeel. We start by presenting the datasets used in this evaluation. In our setting, each dataset consists of a network together with latent profiles for the nodes. Hence, we first introduce the networks, before explaining our approach for obtaining latent profiles.

6.1 Networks. Of our collections of networks, two consist of subgraphs extracted from the DBLP coauthorship database,2 where vertices represent researchers, and edges represent co-authorship relations. Specifically, we extracted the ego-nets of radius 2 for some selected high-profile computer scientists. The resulting ego-nets form the collection denoted as DBLP.E2. We also consider the subgraphs induced by researchers who have published in the ICDM and KDD conferences, respectively, constituting the DBLP.C collection.

Our third collection of networks consists of subgraphs extracted from the Internet Movie Data Base3 where vertices represent actors and edges connect actors who played together in at least one movie. Specifically, we constructed actor networks from this database by considering some well-known directors and production companies, such as Francis F. Coppola or the Warner Bros. Entertainment Inc., and extracting the network induced by their movies. The resulting networks form the collection denoted as IMDB.

In our problem, we are looking for connected subgraphs. If the seed nodes in T -Comm belong to different components, there is obviously no solution. Hence, in our experiments we consider only the largest component of each of the networks.

The statistics of a sample of the networks from these three collections can be found in Table 1. 6.2 Profiles. Besides links, the co-authorship and the co-acting networks contain additional information which we exploit to derive structured profiles, as follows.

In the co-authorship networks, we associate nodes, i.e. researchers, to the conferences in which they published. We then turn this information into profiles by considering the eigenvectors associated to the largest eigenvalues of the incidence matrix of conferences to nodes, scaled to the unit interval. Neighboring researchers in these networks are collaborators who have published papers together. Hence, they published in some of the same conferences, and more generally share similar research interest. Intuitively, they will therefore be assigned similar profile values.

In the co-acting networks, we consider the genres of the movies each actor played in and turn this information into profiles, once again by computing the eigenvectors associated to the largest eigenvalues of the obtained incidence matrices.

The distributions of latent profiles values (x i ) over nodes and of squared weights (w 2 ij ) over edges in the ICDM network are shown in Figure 4.

Evaluation measures

For a solution nodeset V , our main evaluation measure is T (G(V ), X, F) -T (V ) for short -the social tension in the subgraph induced by V with conformed profiles obtained by applying the repeated averaging process over that subgraph.

Two main properties contribute to a solution subgraph having a low social tension (see Equation (3.1)). On one hand, finding a subgraph with few edges results in fewer terms in the sum. On the other hand, finding a subgraph with low tension edges results in small values in the sum. Thus, we compute two auxiliary values that provide insight into the nature of the solutions obtained. Namely, for a solution V we compute the number of edges in the solution, |E(V )|, and the average of the squared edge weights in the solution,

w 2 (V ) = 1 |E(V )| (i,j)∈E(V ) w 2 ij .
Solutions obtained for different seed sets are hardly comparable. Thus, to make the evaluation possible, we standardize the measured values before aggregating them. Specifically, we use the number of edges in the minimum spanning tree connecting the seed nodes, e b , as a comparison basis (and lower bound) for the number of edges in the solution subgraphs, and divide w 2 (V ) by the corresponding average over the whole graph.

Given a solution V , we take the following evaluation measures, for which lower values are more desirable: (iii) the standardized average edge weight (auxiliary measure) σ(V ) = w 2 (V )/w 2 (V ).

6.4 Generating sets of seed nodes. For each dataset, i.e. each pair of network and latent profiles, we run each algorithm with a number of different sets of seed nodes Q. Here we restrict ourselves to sets of seven and four seed nodesfor the co-authorship networks and the co-acting networks respectively, as representative scenarios for the community-search problem.

As we expect the distance between the nodes in the seed set to have an impact on the behavior of the algorithms, we want to sample seed sets across the range of possible distances and to group them based on this criterion. Thus, we generate a thousand seed sets and look at the maximum pairwise distance within each set. We then select at most 30 seed sets from the 10-33%, 33-66%, and 66-90% percentiles of the distance distribution. The resulting three groups of seed sets are denoted as D1, D2 and D3, from tight seed sets to more dispersed ones. Results in Figure 5 are presented aggregated according to these distance groups.

6.5 Single-attribute and multi-attribute profiles. For each latent profile construction scheme, i.e. whether derived from conferences or movie genres (see Section 6.2), we can either consider the column vectors separately, thereby obtaining several single-attribute profiles, where each node is associated to a single profile value, or consider the entire matrix at once thereby obtaining one multi-attribute profile, where each node is associated to a multi-attribute profile vector.

In our experiments, we take the first four columns of the matrix as four separate single-attribute profiles and the entire matrix as one multi-attribute profile (6 and 21 attributes for the DBLP and IMDB datasets, respectively). Results for the C.Papadimitriou network, for single-attribute (left) and multi-attribute (right) latent profiles, are shown in Figure 5. We observe that the algorithms that exploit the profiles of individuals outperform the other two variants in (almost) all cases.

Recall that neither CTree(e) nor CPeel(r) consider the profiles of individuals. All they can do is minimize the social tension by finding a small subgraph to connect the seed nodes. Our results show that they are indeed quite effective at minimizing the number of edges in the reported solutions, typically achieving the lowest values of ε(V ) (middle column in each block of Figure 5). However, CTree(s), CPeel(m), and CPeel(s), the profile-aware variants, find solutions with lower edge weights, i.e. achieving lower values for σ(V ) (right hand side column), at the cost of including extra edges. This gives them an advantage for minimizing social tension, obtaining lower values for τ (V ) (left hand side column).

This pattern clearly holds whether we consider single-attribute or multi-attribute profiles.

CTree(e) CTree(s)

CPeel(m) CPeel(s) CPeel(r) Cocktail τ (V ) ε(V ) σ(V ) τ (V ) ε(V ) σ(V ) D1

Comparison to finding dense communities.

In addition to our proposed algorithms, we also obtain communities by applying the GreedyFast algorithm of Sozio and Gionis [START_REF] Sozio | The community-search problem and how to plan a successful cocktail party[END_REF], denoted here as Cocktail, on the networks with the same sets of seed individuals. The aim of this algorithm is to find a subgraph that connects the seeds while maximizing the minimum degree among selected nodes. This algorithm considers neither profiles nor social tension; Nevertheless, we can compute the tension of the community that consists of the nodes returned as a solution and compare it to the communities obtained with our algorithms. Furthermore, Cocktail requires the user to set a value for the upper bound on the size of the solution. We set this value to k = 200, as it seems to result in reasonable runtimes while allowing the algorithm to construct a solution in most cases. The cases where the algorithm fails to return a solution are left out from our statistics. On the C.Papadimitriou network the solutions returned by Cocktail are comparable in size to those of our CTree(s) algorithm (middle column in each block of Figure 5). The quality of edges selected in its solutions is on par with CTree(e) and CPeel(r) (right hand side column), which are also oblivious to the profiles of individuals. Expectedly, Cocktail appears poorly suited for the task of finding low-tension communities.

6.7 Impact of other factors. Further investigations (details omitted) show variations in the performance of the algorithms depending on the network structure. Indeed, in a high density network, favoring low tension paths as done by CTree(s) can result in many more edges in the induced subgraph, yielding a significantly higher social tension and actually hurting the performance.

We also looked at the impact of the distribution of profile values on the behavior of the algorithms. In order to do so, we constructed random latent profiles under different sampling distributions (e.g. uniform and exponential). We could observe variations between the different random distributions, but these differences appeared to be limited when contrasted with the gap that exists between random and eigenvector profiles. Furthermore, while the profile-aware variants generally tend to pick edges with lower tension at the cost of involving more edges, as discussed earlier, this tendency is more pronounced when handling eigenvector profiles as compared to randomly distributed profiles.

We conclude from these observations that the distribution of profile values has a limited impact compared to the presence of structure in eigenvector profiles and that the profile-aware variants are clearly suited to exploit this structure.

6.8 Running times. Indicative running times of the algorithms on networks of varying sizes and densities, with multi-attribute profiles are listed in Table 1. As expected, the tree-based algorithms are significantly faster than the top-down algorithms, up to two orders of magnitude, and scale much better.

For a comparison between multi-attribute profiles and single-attribute profiles, we look at the running times on the ICDM network with single-attribute profiles:

CTree(e) CTree(s) CPeel(s) CPeel(m) CPeel(r) 0.2 (±0.0) 3.5 (±0.5) 147 (±26.6) 107 (±24.9) 37.0 (±12. [START_REF] Bindel | How Bad is Forming Your Own Opinion?[END_REF] We observe that, also as expected, going from single-attribute to multi-attribute profiles hardly has any impact on the running times of our algorithms.

Conclusions

Problems related to community search have multiple applications in online social media and collaboration networks. In this paper, we add a new modeling angle to this class of problems. The key characteristic of our model is that each node of the social network is not only characterized by its connections and its skills, but also by its profile. These profiles, which change dynamically through a conformation process, give rise to social tension in the network. Given this model, we define the T -Comm problem, where the goal is to identify a set of connected individuals that define a low-tension subgraph. Such a problem arises both in social network and social media mining as well as in human-resource management, where the goal is to find a set of workers who are not only connected, but also will have a potentially fluid collaboration. The contributions of our paper include the formal definition of this problem and the design of algorithms for solving it effectively in practice. Our experimental results with real data from social and collaboration networks highlight the characteristic behavior of the different algorithms variants and illustrate the effect of network structure and profile distribution on the algorithms' relative performance. Finally, our work enables future research combining subgraph mining with dynamic processes occurring among the nodes.

Figure 1 :

 1 Figure 1: Schema of the constructed graph for the reduction from X3C. The black and white nodes have latent profiles with values 1 and 0 respectively.

Proposition 4 . 1 .

 41 The T -Comm problem cannot be solved optimally in polynomial time even with a single attribute (i.e. m = 1) unless P = NP.Proof. (Sketch) We prove the hardness of T -Comm with a reduction from the problem of exact cover by 3-sets.

Figure 2 :

 2 Figure 2: The CTree algorithm for solving T -Comm.

Figure 3 :

 3 Figure 3: The CPeel algorithm for solving T -Comm.

Figure 4 :

 4 Figure 4: Distribution of latent profile values, x i , over nodes (top) and of squared weights, w 2 ij , over edges (bottom) for the ICDM network (eigenv. conferences).

  (i) the standardized social tension (main measure)τ (V ) = T (V )/(2e b • w 2 (V )),(ii) the standardized solution size (auxiliary measure) ε(V ) = |E(V )| /e b , and

D3Figure 5 :

 5 Figure 5: Results for the T -Comm problem on the C.Papadimitriou with single-attribute (left) and ten-attribute (right) latent profiles derived from conferences.

Table 1 :

 1 Average running times (in seconds) of the algorithms (± std. dev.) solving the T -Comm problem on networks of varying number of vertices (|V |), edges (|E|) and average degree densities (δ).

	Network	|V |	|E|	δ	CTree(e)	CTree(s)	CPeel(s)	CPeel(m)	CPeel(r)
	IMDB WarnerBros 1970s	225	1 599 7.11	0.0 (±0.0)	0.1 (±0.0)	0.9 (±0.1)	0.7 (±0.1)	0.1 (±0.1)
	IMDB F.F.Coppola	678	6 306 9.30	0.0 (±0.0)	0.7 (±0.1)	8.8 (±1.6)	6.4 (±1.2)	1.4 (±0.6)
	DBLP.E2 E.Demaine	2 234	7 701 3.45	0.1 (±0.0)	2.8 (±0.3)	75.7 (±12.3) 60.9 (±13.0) 19.2 (±6.2)
	DBLP.E2 C.Papadimitriou	2 613	9 472 3.62	0.1 (±0.0)	3.2 (±0.3) 114.6 (±20.0) 91.6 (±22.0) 31.6 (±9.6)
	DBLP.C ICDM	2 795 10 280 3.68	0.2 (±0.0)	3.3 (±0.3) 163.9 (±28.1) 133.9 (±29.7) 38.9 (±11.2)
	DBLP.C KDD	2 737 11 072 4.05	0.2 (±0.0)	3.5 (±0.2) 166.8 (±27.8) 136.7 (±28.1) 36.0 (±13.0)
	DBLP.E2 P.Yu	4 596 13 250 2.88	0.2 (±0.0)	4.4 (±0.3) 291.3 (±56.3) 242.3 (±43.1) 68.6 (±20.5)
	IMDB WarnerBros	2 111 32 166 15.24	0.3 (±0.1)	3.0 (±0.2) 139.1 (±19.7) 57.2 (±13.0) 22.8 (±9.1)
	IMDB WB+Paramount+Fox	5 758 178 741 31.04	1.4 (±0.2) 15.4 (±1.0) 2192.3 (±346.6) 670.5 (±168.1) 281.6 (±101.6)

An extended version of this paper including the teamformation variant as well as additional experimental results is available at https://arxiv.org/abs/1701.05352.

http://dblp.uni-trier.de/xml/

http://www.imdb.com

Acknowledgements. Most of the work was done while Esther Galbrun and Behzad Golshan were at Boston University. Aristides Gionis is supported by the Finnish Funding Agency for Innovation TEKES (project "Re:Know"), the Academy of Finland (project "Nestor"), and the EU H2020 Program (project "SoBig-Data"). This research was funded by NSF grants: IIS 1320542, IIS 1421759 and CAREER 1253393 as well as a gift from Microsoft.