Mohammad Abouei Mehrizi
email: mohammad.aboueimehrizi@gssi.it

Federico Corò
email: federico.coro@uniroma1.it

Emilio Cruciani
email: emilio.cruciani@inria.fr

D ' Gianlorenzo
email: gianlorenzo.dangelo@gssi.it

Angelo

Election Control through Social Influence with Unknown Preferences

The election control problem through social influence asks to find a set of nodes in a social network of voters to be the starters of a political campaign aiming at supporting a given target candidate. Voters reached by the campaign change their opinions on the candidates. The goal is to shape the diffusion of the campaign in such a way that the chances of victory of the target candidate are maximized. Previous work shows that the problem can be approximated within a constant factor in several models of information diffusion and voting systems, assuming that the controller, i.e., the external agent that starts the campaign, has full knowledge of the preferences of voters. However this information is not always available since some voters might not reveal it. Herein we relax this assumption by considering that each voter is associated with a probability distribution over the candidates. We propose two models in which, when an electoral campaign reaches a voter, this latter modifies its probability distribution according to the amount of influence it received from its neighbors in the network. We then study the election control problem through social influence on the new models: In the first model, under the Gap-ETH, election control cannot be approximated within a factor better than 1/n o(1) , where n is the number of voters; in the second model, which is a slight relaxation of the first one, the problem admits a constant factor approximation algorithm.

Introduction

Social media play a fundamental role in everyone's life providing information, entertainment, and learning. Many social media users prefer to access social network platforms such as Facebook or Twitter before news websites as they provide faster means for information diffusion [START_REF] Eva | News use across social media platforms 2018[END_REF]. As a consequence, online social networks are also exploited as a tool to alter users' opinions. The extent to which the opinions of an individual are conditioned by social interactions is called social influence. It has been observed that social influence starting from a small set of individuals may generate a cascade effect that allows to reach a large part of the network. Recently, this capability has been used to affect the outcome of political elections. There exists evidence of political intervention which shows the effect of social media manipulation on the elections outcome, e.g., by spreading fake news [START_REF] Pennycook | Prior exposure increases perceived accuracy of fake news[END_REF]. A real-life example is in the 2016 US election where a study showed that on average 92% of people remembered pro-Trump fake news and 23% of them remembered pro-Clinton fake news [START_REF] Allcott | Social media and fake news in the 2016 election[END_REF]. Several other cases have been studied [BFJ + 12, Fer17, [START_REF] Kreiss | Seizing the moment: The presidential campaigns' use of twitter during the 2012 electoral cycle[END_REF][START_REF] Stier | Election campaigning on social media: Politicians, audiences, and the mediation of political communication on facebook and twitter[END_REF].

There exists a wide literature about manipulation of voting systems; we point the reader to a recent survey [START_REF] Faliszewski | Control and bribery in voting[END_REF]. Despite that, only few studies focus on the problem of controlling the outcome of political elections through the spread of information in social networks. The election control problem [START_REF] Wilder | Controlling elections through social influence[END_REF] consists in selecting a set of nodes of a network to be the starters of a diffusion with the aim of maximizing the chances for a target candidate to win an election. In particular, in the constructive election control problem, the goal is to maximize the Margin of Victory (MoV) of the target candidate on its most critical opponent, i.e., the difference of votes (or score, depending on the voting system) between the two candidates after the effect of social influence. A variation of the problem, known as destructive election control, aims at making a target candidate lose. Both problems have been originally analyzed under the Independent Cascade Model (ICM) [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF], and considering plurality voting; approximation and hardness-of-approximation results are provided [START_REF] Wilder | Controlling elections through social influence[END_REF]. Corò et al. [START_REF] Corò | Exploiting social influence to control elections based on scoring rules[END_REF][START_REF] Corò | Vote for me!: Election control via social influence in arbitrary scoring rule voting systems[END_REF] analyzed the problem in arbitrary scoring rules voting systems under the Linear Threshold Model (LTM) [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF], providing constant factor approximation algorithms. It has been later shown that it is NP -hard to find any constant factor approximation in the multi-winner scenario [START_REF] Abouei | Multi-winner election control via social influence[END_REF].

Faliszewski et al. [START_REF] Faliszewski | Opinion diffusion and campaigning on society graphs[END_REF] examine bribery in an opinion diffusion process with voter clusters: each node is a cluster of voters, represented as a weight, with a specific list of candidates; there is an edge between two nodes if they differ by the ordering of a single pair of adjacent candidates. The authors show that making a specific candidate win in their model is NP -hard and fixed-parameter tractable with respect to the number of candidates. Bredereck et al. [START_REF] Bredereck | Manipulating opinion diffusion in social networks[END_REF] studied the problem of manipulating diffusion on social networks, though not specifically in the context of elections. They show that identifying successful manipulation via bribing, adding/deleting edges, or controlling the order of asynchronous updates are all computationally hard problems. A similar approach is taken by Apt et al. [START_REF] Krzysztof | Social networks with competing products[END_REF], where the authors introduce a threshold model for social networks in order to characterize the role of social influence in the global adoption of a commercial product.

Contribution. In all previous works it is assumed that the controller knows the preference list of each voter. However, this assumption is not always satisfied in realistic scenarios as voters may not reveal their preferences to the controller. Herein, in Section 2, we introduce two new models, Probabilistic Linear Threshold Ranking (PLTR) and Relaxed-PLTR (R-PLTR), that encompass scenarios where the preference lists of the voters are not fully revealed. Specifically, we use an uncertain model in which the controller only knows, for each voter, a probability distribution over the candidates. In fact, in applied scenarios, the probability distribution could be inferred by analyzing previous social activity of the voters, e.g., re-tweets or likes of politically oriented posts. We envision that some given focused news about a target candidate spread through the network as a message. We model such a diffusion via the LTM [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF]. The message will have an impact on the opinions of voters who received it from their neighbors, leading to a potential change of their vote if the neighbors exercise a strong influence on them. With this intuition in mind, in our models, the probability distribution of the voters reached by the message is updated as a function of the degree of influence that the senders of the message have on them. The rationale is that the controller, without knowing the exact preference list which is kept hidden, can just update its estimation on it by considering the mutual degree of influence among voters. We acknowledge that our models do not cover all scenarios that can arise in election control, e.g., messages about multiple candidates. However they represent a first step towards modeling uncertainty.

We study on our models both the constructive and destructive election control problems. We show in Section 3 that the election control problem in PLTR is at least as hard to approximate as the Densest-k-Subgraph problem [START_REF] Manurangsi | Almost-polynomial ratio eth-hardness of approximating densest k-subgraph[END_REF]. This result implies several conditional hardness of approximation bounds for our problem, for example it cannot be approximated within any constant factor, unless the Unique Game Conjecture holds and it cannot be approximated to within any polynomial factor if the Exponential Time Hypothesis holds. However, these hardness of approximation bounds do not hold for the election control problem in R-PLTR, for which we can show that the problem remains NP -hard.

In Section 4 we provide an algorithm that guarantees a constant factor approximation to the constructive and destructive election control problems in R-PLTR. In the relaxed model, R-PLTR, also "partially-influenced" nodes change their probability distribution. Although this simple modification is enough to make the problem substantially easier, preliminary experimental results show that the hardness of approximation for PLTR is purely theoretical and is due to hard instances in the reduction.

In Section 5 we present the simulation of our models and algorithm on two real-world datasets.

Influence Models and Problem Statement

Background. Influence Maximization is the problem of finding a subset of the most influential users in a social network with the aim of maximizing the spread of information given a particular diffusion model. In this work, we focus on the diffusion model known as Linear Threshold Model (LTM) [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF]. Given a graph G = (V, E), each edge (u, v) ∈ E has a weight b uv ∈ [0, 1], each node v ∈ V has a threshold t v ∈ [0, 1] sampled uniformly at random and independently from the others, and the sum of the weights of the incoming edges of v is (u,v)∈E b uv ≤ 1. Each node can be either active or inactive. Let A 0 be a set of initially active nodes and A t be the set of nodes active at time t. A node v becomes active if the sum of the incoming active weights at time t -1 is greater than or equal to its threshold t v , i.e., v ∈ A t if and only if v ∈ A t-1 or

u∈A t-1 :(u,v)∈E b uv ≥ t v .
The process terminates at the first time t in which the set of active nodes would not change in the next round, i.e., A t = A t+1 . We define the eventual set of active nodes as A := A t and the expected size of A as σ(A 0 ). Given a budget B, the influence maximization problem consists in finding a set of nodes A 0 of size B, called seeds, in such a way that σ(A 0 ) is maximum.

Kempe et al. [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF] showed that the distribution of active nodes A, for any set A 0 , is equal to the distribution of the sets of nodes that are reachable from A 0 in the set of random graphs called live-edge graphs. A live-edge graph is a subgraph in which each node has at most one incoming edge. Even if the number of live-edge graphs is exponential, by using standard Chernoff-Hoeffding bounds, it is possible to compute a (1 ± )-approximation of σ(A 0 ), for a given A 0 , with high probability by sampling a polynomial number of live-edge graphs. Moreover, σ(A 0 ) is monotone and submodular w.r.t. to the initial set A 0 ; hence, an optimal solution can be approximated to a factor of 1 -1/e using a simple greedy algorithm [START_REF] Nemhauser | An analysis of approximations for maximizing submodular set functions-I[END_REF]. There has been intensive research on the problem in the last decade. We point the reader to a recent survey on the topic [START_REF] Li | Influence maximization on social graphs: A survey[END_REF].

Notation. Let G = (V, E) be a directed graph representing a social network of voters and their interactions. We denote the set of m candidates running for the election as C = {c 1 , c 2 , . . . , c m } and the target candidate as c ∈ C. Each node v ∈ V has a probability distribution over the candidates π v , where π v (c i ) is the probability that v votes for candidate c i ; then for each v ∈ V we have that π v (c i ) ≥ 0 for each candidate c i and m i=1 π v (c i ) = 1. Moreover, we denote by N - v and N + v , respectively, the sets of incoming and outgoing neighbors for each node v ∈ V . For each candidate c i , we assume that π v (c i ) is at least a polynomial fraction of the number of voters, i.e., π v (c i ) = Ω(1/|V | γ ) for some constant γ > 0.1 Let X v (c i ) be an indicator random variable, where X v (c i ) = 1 if v votes for c i , with probability π v (c i ), and X v (c i ) = 0 otherwise. We define the expected score of a candidate c i as the expected number of votes that c i obtains from the voters

F (c i , ∅) := E v∈V X v (c i ) = v∈V π v (c i ).
PLTR Model. As in LTM, each node v has a threshold t v ∈ [0, 1]; each edge (u, v) ∈ E has a weight b uv , that models the influence of node u on v, with the constraint that, for each node v, u:(u,v)∈E b uv ≤ 1. We assume the weight of each existing edge (u, v) not to be too small, i.e., b uv = Ω(1/|V | γ ) for some constant γ > 0. 4 Given an initial set of seed nodes S, the diffusion process proceeds as in LTM: Inactive nodes become active if the sum of the weights of incoming edges from active neighbors is greater than or equal to their threshold. Mainly, we are modeling the spread of some ads/news about the target candidate: Active nodes receive the message and spread it to their neighbors. Moreover, in PLTR, active nodes are influenced by the message, increasing their probability of voting for the target candidate. In particular, an active node v increases the probability of voting for c by an amount equal to the sum of the weights of its edges incoming from other active nodes, i.e., it adds u∈A∩N - v b uv to the initial probability π v (c ). Then it normalizes to maintain π v as a probability distribution. Formally, for each node v ∈ A, where A is the set of active nodes at the end of LTM, the preference list of v is denoted as πv and it is equal to:

πv (c ) = π v (c ) + u∈A∩N - v b uv 1 + u∈A∩N - v b uv and πv (c i ) = π v (c i ) 1 + u∈A∩N - v b uv , (1)
for each

c i = c . All inactive nodes v ∈ V \ A will have πv (c i ) = π v (c i )
for all candidates, including c . As for the expected score before the process, we can compute the expected final score of a candidate c i as

F (c i , S) := E v∈V X v (c i , S) = v∈V πv (c i ),
where X v (c i , S) is the indicator random variable after the process, i.e., X v (c i , S) = 1 if v votes for c i , with probability πv (c i ), and X v (c i , S) = 0 otherwise.

Let us denote by G the set of all possible live-edge graphs sampled from G. We can also compute F (c i , S) by means of live-edge graphs used in the LTM model as

F (c i , S) = G ∈G F G (c i , S) • P(G ), (2)
where F G (c i , S) is the score of c i in G ∈ G and P(G ) is the probability of sampling live-edge G . More precisely, for the target candidate we have

F G (c , S) = v∈R G (S) π v (c )+ u∈R G (S)∩N - v b uv 1 + u∈R G (S)∩N - v b uv + v∈V \R G (S) π v (c ),
where R G (S) is the set of nodes reachable from S in G . A similar formulation can be derived for c i = c . R-PLTR Model. In the next section we prove that the election control problem in PLTR is hard to approximate to within a polynomial fraction of the optimum (Theorem 1). However, we show that a small relaxation of the model allows us to approximate it to within a constant factor.

In the relaxed model, that we call Relaxed Probabilistic Linear Threshold Ranking (R-PLTR), the probability distribution of a node is updated if it has at least an active incoming neighbor (also if the node is not active itself). More formally, every node v ∈ V (and not just every node v ∈ A as in PLTR) changes its preference by updating its probability distribution via Eq. ( 1); thus also nodes that have at least an active incoming neighbor can change. The rationale is that a voter might slightly change its opinion about the target candidate if it receives some influence from its active incoming neighbors even if the received influence is not enough to activate it (thus making it propagate the information to its outgoing neighbors). Therefore, we include this small amount of influence in the objective function. In the next section, we show that election control in R-PLTR is still NP -hard, and then we give an algorithm that guarantees a constant approximation ratio in this setting.

Problem Statement. In the constructive election control problem we maximize the expected Margin of Victory (MoV) of the target candidate w.r.t. its most voted opponent, akin to [START_REF] Corò | Exploiting social influence to control elections based on scoring rules[END_REF][START_REF] Wilder | Controlling elections through social influence[END_REF]. We define the MoV(S) obtained starting from S as the expected increase, w.r.t. the value before the process, of the difference between the score of c and that of the most voted opponent. 2 Formally, if c and ĉ are respectively the candidates different from c with the highest score before and after the diffusion process

MoV(S) := F (c, ∅) -F (c , ∅) -(F (ĉ, S) -F (c , S)) . (3)
Given a budget B, the constructive election control problem asks to find a set of seed nodes S, of size at most B, that maximizes MoV(S). It is worth noting that MoV can also be expressed as a function of the score gained by candidate c and the score lost by its most voted opponent ĉ at the end of the process. We define the score gained and lost by a candidate c i as

g + (c i , S) := F (c i , S) -F (c i , ∅), g -(c i , S) := F (c i , ∅) -F (c i , S).
Therefore, we can rewrite MoV(S) as

MoV(S) = g + (c , S) + g -(ĉ, S) -F (ĉ, ∅) + F (c, ∅). (4)
The destructive election control problem, instead, aims at making the target candidate lose by minimizing its MoV. In this dual scenario, the probability distributions of the voters are updated slightly differently in our models, i.e., influenced voters have a lower probability of voting for the target candidate c mimicking the spread of "negative" news about c .

Influencing Voters About Other Candidates. In our model the controller can send to the seed nodes a message in support of only one single candidate, e.g., latest news about the candidate. We prove that the best strategy is that of sending messages in support of the target candidate c , i.e., if the controller wants c to win, then, according to our models, the direct strategy of targeting voters with news about c is more effective than the alternative strategy of distracting the same voters with news about other candidates. Indeed, it is not always sufficient to maximize the score of the target candidate to ensure his victory or to maximize the margin of victory, and it is easy to find counter-examples of this strategy. Moreover, in the models of Wilder et al. [START_REF] Wilder | Controlling elections through social influence[END_REF] and Corò et al. [START_REF] Corò | Exploiting social influence to control elections based on scoring rules[END_REF] it could be convenient to increase the score of a third candidate in order to make the most voted opponent w.r.t. c lose score and favor c .

However, as previously claimed, in our models this does not hold. In fact, we can distinguish between the three possible strategies:

• MoV 1 : Influencing voters about c .

• MoV 2 : Influencing voters about ĉ, i.e., the most voted opponent w.r.t. c at the end of the process.

• MoV 3 : Influencing voters about any other candidate c.

Let us now analyze the MoV of c in these three different cases. As described in Equation ( 4), a general formulation for MoV is the following

MoV(S) := g + (c , S) + g -(ĉ, S) + ∆ = F (c , S) -F (c , ∅) + F (ĉ, ∅) -F (ĉ, S) + ∆,
where S is the initial set of seed nodes and ∆ is the sum of constant terms that are not modified by the process. With some algebra, it is possible to compute the MoV of c in such scenarios, getting the following formulations:

• MoV 1 (S) = v∈A (1 + π v (ĉ) -π v (c )) u∈A∩N - v b uv 1 + u∈A∩N - v b uv + ∆; • MoV 2 (S) = v∈A (π v (ĉ) -π v (c ) -1) u∈A∩N - v b uv 1 + u∈A∩N - v b uv + ∆; • MoV 3 (S) = v∈A (π v (ĉ) -π v (c )) u∈A∩N - v b uv 1 + u∈A∩N - v b uv + ∆.
We just need to observe that MoV 1 (S) ≥ MoV 2 (S) and that MoV 1 (S) ≥ MoV 3 (S) to conclude that it is always convenient to influence the voters about the target candidate whenever you want to maximize the MoV of c . Therefore, in the remainder of the paper, we only focus on changing the score of the target candidate c . Note that the observations above hold both for PLTR and R-PLTR.

Hardness Results

In this section we provide two hardness results related to election control in PLTR and R-PLTR.

In Theorem 1 we show that maximizing the MoV in PLTR is at least as hard to approximate as the Densest-k-subgraph problem. This implies several conditional hardness of approximation bounds for the election control problem. Indeed, it has been shown that the Densest-k-subgraph problem is hard to approximate: to within any constant bound under the Unique Games with Small Set Expansion conjecture [START_REF] Raghavendra | Graph expansion and the unique games conjecture[END_REF]; to within n -1/(log log n) c , for some constant c, under the exponential time hypothesis (ETH) [START_REF] Manurangsi | Almost-polynomial ratio eth-hardness of approximating densest k-subgraph[END_REF]; to n -f (n) for any function f ∈ o(1), under the Gap-ETH assumption [START_REF] Manurangsi | Almost-polynomial ratio eth-hardness of approximating densest k-subgraph[END_REF]. Then, in Theorem 2, we show that maximizing the MoV in R-PLTR is still NP -hard.

Theorem 1. An α-approximation algorithm to the election control problem in PLTR gives an αβ-approximation to the Densest k-Subgraph problem, for a positive constant β < 1.

Proof. Given an undirected graph G = (V, E) and an integer k, Densest k-Subgraph (DkS) is the problem of finding the subgraph induced by a subset of V of size k with the highest number of edges given that k is fixed.

The reduction works as follows: Consider the PLTR problem on G, where each undirected edge {u, v} is replaced with two directed edges (u, v) and (v, u). Let us consider m candidates and assume that all nodes initially have null probability of voting for all the candidates but one, different from c , that we denote as ĉ. Formally we have that, π v (ĉ) = 1 and π v (c i ) = π v (c ) = 0 for each c i = ĉ and for each v ∈ V . Assign to each edge (u, v) ∈ E a weight b uv = 1 n γ , for any fixed constant γ ≥ 4 and n = |V |.

We show the reduction considering the problem of maximizing the score, because in the instance considered in the reduction the MoV is exactly equal to twice the score. In fact, the score of ĉ after PLTR starting from any initial set S is

F (ĉ, S) = v∈V πv (ĉ) = v∈V \A π v (ĉ) + v∈A πv (ĉ) = |V | -|A| + v∈A 1 1 + u∈A∩N - v 1 n γ = |V | - v∈A 1 - 1 1 + u∈A∩N - v 1 n γ = |V | - v∈A u∈A∩N - v 1 n γ 1 + u∈A∩N - v 1 n γ = |V | -F (c , S), because ( u∈A∩N - v 1 n γ )/(1 + u∈A∩N - v 1 n γ ) = πv (c ) and π v (c ) = 0 for each v ∈ V .
Thus, according to the definition of MoV in Equation (6), we have that

MoV(S) = |V | -(|V | -F (c , S) -F (c , S)) = 2F (c , S).
To compute the expected final score of the target candidate we average its score in all live live-edge graph in G, according to Formula (3). In our reduction, the empty live-edge graph G ∅ = (V, ∅) is sampled with high probability, i.e., with probability at least 1 -1 n γ-2 :

P G ∅ = v∈V   1 - u∈N - v b uv   = v∈V 1 - |N - v | n γ ≥ v∈V 1 - 1 n γ-1 = 1 - 1 n γ-1 n (a) = n i=0 n i (1) n-i -1 n γ-1 i = n i=0 n i (-1) i n i(γ-1) (b) ≥ n 0 - n 1
1 n γ-1 + n/2 i=2 n i 1 n 2i(γ-1) - n i + 1 1 n (2i+1)(γ-1) (c) ≥ 1 - 1 n γ-2
where in (a) we used the binomial expansion, (b) is due to last negative term in the lhs that does not appear in the rhs when n is even, and (c) is due to

n i 1 n 2i(γ-1) ≥ n i + 1 1 n (2i+1)(γ-1) , for any γ ≥ 2. Since P G ∅ ≤ 1, then P G ∅ = Θ(1). Moreover, G =G ∅ P (G ) = O 1 n γ-2
The score obtained by c in a live-edge graph G starting from any initial set of seed nodes S is

F G (c , S) = v∈R G (S) π v (c ) + u∈R G (S)∩N - v 1 n γ 1 + u∈R G (S)∩N - v 1 n γ = Θ   1 n γ v∈R G (S) |R G (S) ∩ N - v |   , since 1 ≤ 1+ u∈R G (S)∩N - v 1 n γ ≤ 2 for each v ∈ R G (S). Also, note that v∈R G (S) |R G (S)∩ N -
v | is equal to the number of edges of the subgraph induced by the set R G (S) of nodes reachable from S in G , which is not greater than n 2 , and thus F G (c , S) = O 1 n γ-2 . Note that in the empty live edge graph G ∅ the set R G ∅ (S) at the end of LTM is equal to S, since the graph has no edges. Thus

F G ∅ (c , S) = 1 n γ • v∈S |S ∩ N - v | 1 + u∈S∩N - v 1 n γ
and since the denominator is, again, bounded by two constants we have that

F G ∅ (c , S) = Θ v∈S |S ∩ N - v | n γ = Θ SOL DkS (S) n γ ,
where SOL DkS (S) := v∈S |S ∩ N - v | is the number of edges of the subgraph induced by S, i.e., the value of the objective function of DkS for solution S.

Thus, the expected final score of the target candidate is

F (c , S) = G ∈G F G (c , S) • P(G ) = F G ∅ (c , S) • P(G ∅ ) + G =G ∅ F G (c , S) • P(G ). Since F G (c , S) and G =G ∅ P (G ) are in O 1 n γ-2 , then G =G ∅ F G (c , S) • P(G ) = O 1 n γ-2 G =G ∅ P(G ) = O 1 n 2(γ-2) = O SOL DkS (S) n γ ,
for any γ ≥ 4. Thus

F (c , S) = Θ SOL DkS (S) n γ • Θ(1) + O SOL DkS (S) n γ which means that F (c , S) = Θ SOL DkS (S) n γ
. We apply the Bachmann-Landau definition of Θ notation: There exist three positive constants n 0 , β 1 , and β 2 such that, for all n > n 0 ,

β 1 SOL DkS (S) n γ ≤ F (c , S) ≤ β 2 SOL DkS (S) n γ .
Note that, in this case, the constants n 0 , β 1 , and β 2 do not depend on the specific instance. Since the previous bounds hold for any set S we also have that

β 1 OPT DkS n γ ≤ OPT ≤ β 2 OPT DkS n γ
, where OPT is the value of an optimal solution for PLTR and OPT DkS is the value of an optimal solution for DkS.

Suppose there exists an α-approximation algorithm for PLTR, i.e., an algorithm that finds a set S s.t. the value of its solution is MoV(S) = 2F (c , S) ≥ α • OPT. Then,

α 2 • β 1 OPT DkS n γ ≤ α 2 • OPT ≤ F (c , S) ≤ β 2 SOL DkS (S) n γ . Thus SOL DkS (S) ≥ α 2 β 1 β 2 OPT DkS , i.e., it is an αβ 1 2β 2 -approximation to DkS.
As a corollary of Theorem 1 we get the conditional hardness of approximation bounds stated at the beginning of this section.

Theorem 2. Election control in R-PLTR is NP -hard.

Proof. We prove the hardness by reduction from Influence Maximization under LTM, which is known to be NP -hard [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF].

Consider an instance I LTM = (G, B) of Influence Maximization under LTM. I LTM is defined by a weighted graph G = (V, E, w) with weight function w : E → [0, 1] and by a budget B. Let I R-PLTR := (G , B) be the instance that corresponds to I LTM on R-PLTR, defined by the same budget B and by a graph G = (V , E , w ) that can be built as follows:

Let S be the initial set of seed nodes of size B that maximizes I LTM and let A be the set of active nodes at the end of the process. The value of the MoV obtained by S in I R-PLTR is MoV(S) = |V | -|V \ A|. Indeed, each node v ∈ V in G has πv (c ) = π v (c ) = 1, because the probability of voting for the target candidate remains the same after the normalization. Moreover, each node v i ∈ V ∩ A influences its duplicate v |V |+i with probability 1 and therefore

πv |V |+i (c ) = (π v |V |+i (c )+1)/2 = 1 2 . Therefore, F (c , ∅) = F (c 1 , ∅) = |V |, F (c , S) = |V |+ 1 2 |A|, and F (c 1 , S) = |V \ A| + 1 2 |A|.
Let S be the initial set of seed nodes of size B that achieves the maximum in I R-PLTR . Without loss of generality, we can assume that S ⊆ V , since we can replace any seed node v |V |+i in V \ V with its corresponding node v i in V without decreasing the objective function. If A is the set of active nodes at the end of the process, then by using similar arguments as before, we can prove that MoV(S) = |V | -|V \ A|. Let us assume that S does not maximize I LTM , then, S would also not maximize I R-PLTR , which is a contradiction since S is an optimal solution for I R-PLTR .

We can prove the NP -hardness for the case of maximizing the score by using the same arguments. In fact, notice that maximizing the score of c , i.e., F (c , S) = |V | + 1 2 |A|, is exactly equivalent to maximize the cardinality of the active nodes in LTM.

Approximation Results

In this section, we first show that we can approximate the optimal MoV to within a constant factor by optimizing the increment in the score of c . In detail we show that, given two solutions S * and S * * such that g + (c , S * ) and MoV(S * * ) are maximum, then MoV(S * ) ≥ 1 3 MoV(S * * ). Indeed, we show a more general statement that is: If a solution S approximates g + (c , S * ) within a factor α, then MoV(S) ≥ α 3 MoV(S * * ). Then we show that a simple greedy hill-climbing approach (Algorithm 1) gives a constant factor approximation to the problem of maximizing g + (c , S), where the constant is 1 2 (1 -1 e ). By combining the two results, we get a 1 6 (1-1 e )-approximation algorithm for the election control problem in R-PLTR.

The next theorem generalizes [WV18, Theorem 5.2] as it holds for any scoring rule and for any model in which we have the ability to change only the position of c in the lists of a subset of voters and the increment in score of c is at least equal to the decrement in scoring of the other candidates. Theorem 3. An α-approximation algorithm for maximizing the increment in score of a target candidate gives an α 3 -approximation to the election control problem. Proof. Let us consider two solutions S and S * for the problem of maximizing the MoV for candidate c , with S * as the optimal solution to this problem. These solutions arbitrarily select a subset of voters and modify their preference list changing the score of c . Let us fix c and ĉ, respectively, as the candidates different from c with the highest score before and after the solution S is applied. Assume there exists an α-approximation to the problem of maximizing the increment in score of the target candidate; if we do not consider the gain given by the score lost by the most voted opponent, we have that

MoV(S) = g + (c , S) + g -(ĉ, S) -F (ĉ) + F (c) ≥ αg + (c , S * ) -F (ĉ) + F (c) ≥ α 3 [g + (c , S * ) + g -(c, S * ) + g -(ĉ, S * )] -F (ĉ) + F (c),
where the last inequality holds because g + (c , S) ≥ g -(c i , S) for any solution S and candidate c i since S modifies only the score of c , increasing it, while the score of all the other candidates is decreased, and the increment in score to c * is equal to the sum of the decrement in score of all the other candidates. Since F (ĉ) ≤ F (c), we have that

MoV(S) ≥ α 3 [g + (c , S * ) + g -(c, S * ) + F (c) + g -(ĉ, S * ) -F (ĉ) + F (c) -F (c)] = α 3 [MoV(S * ) + g -(ĉ, S * ) -F (ĉ) + F (c)],
where c is the candidate with the highest score after the solution S * is applied. By definition of c we have that F (c, S * ) ≥ F (ĉ, S * ), which implies that

g -(c, S * ) -g -(ĉ, S * ) = F (c) -F (c, S * ) -F (ĉ) + F (ĉ, S * ) ≤ F (c) -F (ĉ).
Thus, g -(ĉ, S * ) -F (ĉ) + F (c) ≥ 0 and we conclude that MoV(S) ≥ α 3 MoV(S * ).

Constructive Election Control in R-PLTR. Next theorem shows how to get a constant factor approximation to the problem of maximizing the MoV in R-PLTR by reducing the problem to an instance of the weighted version of the influence maximization problem with LTM [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF]. This extension of the LTM, associates to each node a non-negative weight (w : V → R + ) that captures the importance of activating that node. The goal is to find the initial seed set in order to maximize the sum of the weights of the active nodes at the end of the process, i.e., finding arg max S σ w (S) = E v∈A w(v) , where w is a weight function over the node set. A simple hill-climbing greedy algorithm achieves a (1 -1/e)-approximation if the weights are polynomial (or polynomially small) in the number of nodes of the graph and the number of live-edge graph samples is polynomially large in the weights [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF]. 3 Intuitively, if a node has an exponentially small probability of being sampled in the live-edge graph associated with a high weight, then a polynomial number of samples would not be enough to consider it in the solution with non-negligible probability. We exploit this result to approximate the MoV via Algorithm 1, reducing the problem of maximizing the score to that of maximizing σ w (S) in the weighted LTM. We define a new graph Ĝ with the same sets of nodes and edges of G. Then, we assign a weight to each node v ∈ V equal to w(v)

:= u∈N + v b vu (1 -π u (c ))
. Note that we are able to correctly approximate the value of σ w (S) using such weights since by hypothesis on the model b uv ≥ 1 |V | γ 1 , for each (u, v) ∈ E and for some constant γ 1 > 0, and since

π v (c i ) ≥ 1 |V | γ 2
, for each v ∈ V for some constant γ 2 > 0. By applying a multiplicative form of the Chernoff bound we can get a 1 ± approximation of σ w (S), with high probability [KKT15, Proposition 4.1].

Thus, we can use Algorithm 1 to maximize the influence on Ĝ. The algorithm starts with an empty set S and adds to it, in each of B rounds, the node v with maximal marginal gain w.r.t. the solution computed so far. Theorem 4. Algorithm 1 guarantees a 1 6 (1 -1 e )-approximation factor to constructive election control in R-PLTR.

Proof. We first prove that Algorithm 1 gives an 1 2 (1 -1 e )-approximation to the problem of maximizing the increment in score of the target candidate c in R-PLTR. Let S and S respectively be the set of initial seed nodes found by the greedy algorithm and the optimal one. We have that

g + (c , S) = F (c , S) -F (c ) = v∈V π v (c ) + u∈A∩N - v b uv 1 + u∈A∩N - v b uv - v∈V π v (c ) = v∈V (1 -π v (c )) u∈A∩N - v b uv 1 + u∈A∩N - v b uv
and, since the denominator is at most 2, that

g + (c , S) ≥ 1 2 v∈V (1 -π v (c )) u∈A∩N - v b uv = 1 2 u∈A v∈N + u b uv (1 -π v (c )),
where A is the set of active nodes at the end of the process. Note that u∈A v∈N + u b uv (1 -π v (c )) is exactly the objective function that the greedy algorithm maximizes. Hence, using the result by Kempe et al. [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF] we know that

u∈A v∈N + u b uv (1 -π v (c )) ≥ 1 - 1 e u∈A v∈N + u b uv (1 -π v (c )),
where A is the set of active nodes at the end of the process starting from S . Therefore g + (c , S) ≥ 1 2 (1 -1/e) g + (c , S ) since

g + (c , S ) = v∈V (1 -π v (c )) u∈A ∩N - v b uv 1 + u∈A ∩N - v b uv ≤ u∈A v∈N + u b uv (1 -π v (c )),
where the inequality holds since all the denominators in g + (c , S ) are at least 1. Thus, Algorithm 1 achieves a 1 2 1 -1 e -approximation to the maximum increment in score. Using Theorem 3 we get a 1 6 1 -1 e -approximation for the MoV.

Destructive Election Control in R-PLTR. The destructive election control problem is similar to the constructive problem, but in this scenario, in our models, the probability that a voter v votes for c decreases depending on the amount of influence received by v and the loss of probability of c is evenly split over all the other candidates. In this way, we avoid negative values and values that do not sum to 1. In detail, if A is the set of active nodes at the end of LTM, then, for each v ∈ V , the preference list π v changes as follows: where S is the initial set of seed nodes and ∆ = F (ĉ, ∅) -F (c, ∅) is the sum of constant terms that are not modified by the process. Note that maximizing MoV D is NP -hard (it can be proved with a similar argument to that of Theorem 2).

πv (c ) = π v (c ) 1 + u∈A∩N - v b uv and πv (c i ) = π v (c i ) + 1 m-1 u∈A∩N - v b uv 1 + u∈A∩N - v b uv for each c i = c .
Similarly to the constructive case, we define a new graph Ĝ with the same sets of nodes and edges of G. Then, we assign a weight to each node v ∈ V equal to w(v) := u∈N + v b vu π u (c ) and we run Algorithm 1 to find a seed set that approximates the maximum expected weight of active nodes.

Theorem 5. Algorithm 1 guarantees a 1 4 (1-1 e )-approximation factor to the destructive election control in R-PLTR.

Proof. We first prove that Algorithm 1 achieves an 1 2 (1-1 e ) approximation factor to the problem of maximizing the decrease in score of the target candidate c in R-PLTR. Let S and S respectively be the set of initial seed nodes found by the greedy algorithm and the optimal one. Let g - D (c , S) be the decrease in score of candidate c with solution S, i.e., g - D (c , S) = F (c , ∅) -F (c , S). Let A be the set of active nodes at the end of the process; then we have that

g - D (c , S) = v∈V π v (c ) u∈A∩N - v b uv 1 + u∈A∩N - v b uv and, since the denominator is at most 2, that g - D (c , S) ≥ 1 2 v∈V   π v (c ) u∈A∩N - v b uv   = 1 2 u∈A v∈N + u π v (c ) • b uv .
Note that u∈A v∈N + u π v (c )•b uv is exactly the objective function of the greedy Algorithm that maximizes the weighted-LTM for Ĝ. Hence, using the result by Kempe et al. [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF], we know that

u∈A v∈N + u b uv π v (c ) ≥ 1 - 1 e u∈A v∈N + u b uv π v (c ),
where A is the optimal set of active nodes, i.e., the set of active nodes at the end process starting from S (S the optimal solution for the weighted-LTM). Therefore

g - D (c , S) ≥ 1 2 1 - 1 e g - D (c , S ) because g - D (c , S ) = v∈V π v (c ) u∈A ∩N - v b uv 1 + u∈A ∩N - v b uv ≤ v∈V π v (c ) u∈A ∩N - v b uv = u∈A v∈N + u b uv π v (c ),
where the inequality is due to the fact that the denominator in all the terms of g - D (c , S ) is at least 1. Thus we achieve a 1 2 1 -1 e -approximation to the maximum increment in score. Let us fix c and ĉ, respectively, as the candidates different from c with the highest score before and after the solution S is applied; let c be the most voted opponent after the optimal solution S * is applied. Then we have that

MoV(S) = g - D (c , S) + g + D (ĉ, S) + F (ĉ, ∅) -F (c, ∅) ≥ 1 2 1 - 1 e g - D (c , S * ) + g + D (ĉ, S) + F (ĉ, ∅) -F (c, ∅) ≥ 1 4 1 - 1 e g - D (c , S * ) + g + D (c, S * ) + g + D (ĉ, S) + F (ĉ, ∅) -F (c, ∅) = 1 4 1 - 1 e MoV(S * ) + g + D (ĉ, S) + F (ĉ, ∅) -F (c, ∅) ≥ 1 4 1 - 1 e MoV(S * ),
where the last inequality holds since, by definition of c and ĉ, we have that g + D (ĉ, S) + F (ĉ, ∅) ≥ g + D (c, S) + F (c, ∅).

Simulations

We simulate our model on two real-world social networks 4 on which political campaigning messages could spread:

• polbooks: an undirected network with 105 nodes and 882 edges where nodes are political books and edges represent co-purchasing behavior; nodes are labeled as "liberal," "conservative," or "neutral."

• polblogs: a directed network with 1,224 nodes and 19,025 edges where nodes are web blogs about US politics and edges hyperlinks connecting them; nodes are labeled as "liberal" or "conservative."

The number of candidates in our simulations is based on the ground truth of the datasets; as mentioned earlier, polbooks has three clusters and polblogs has two clusters based on different US political parties. We set the probability of each node v to vote for, say, a "liberal" candidate proportionally to the number of neighbors labeled as "liberal," i.e., we set π v (c) = |Nv∩B| |Nv| where c is the "liberal" candidate, B is the set of nodes labeled as "liberal," and N v is the set of neighbors of v. For each node v we sampled the "non-incoming influence weight" bv uniformly at random in [0, 1] and assigned the remaining influence weight uniformly among its incoming neighbors, i.e., we assigned to each edge (u, v) a weight b uv = 1-bv

|N i v | .
In our simulations, we run GreedyScore (Algorithm 1) for the election control problem in R-PLTR. Then, we measure the score and the MoV of each candidate using as starting seed nodes the ones found by the algorithm both in PLTR and in R-PLTR. We run the simulation considering each different candidate as the target one to cover multiple scenarios, considering as budget values the ones in {0, 1, 5, 10}. Then, as baseline to compare, we also considered as seed nodes the most influential ones, i.e., the nodes selected by GreedyIM, the classical greedy algorithm for Influence Maximization [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF].

For the implementation, we used .Net framework 4.6.2 and C# programming language. We have implemented five different classes for managing the graph, the LTM process, the PLTR process, and a GUI. We execute the simulations on a system with the following specifications: CPU Intel Core i7-6700HQ 2.6 GHz, with 4 × 32 KB 8-way L1 (data and inst) cache, and 4 × 256 KB 4-way L2 cache, and 6 MB 12-way L3 cache, RAM 16G DDR4. Each simulation has a running time of approximately 40 seconds for poolbooks and 140 minutes for polblogs.

The results relative to the scores are shown in Figures 1 and2. As expected, the effect of our algorithm in R-PLTR is amplified compared to PLTR, since it affects a greater number of 4 The datasets are taken from http://networkrepository.com/ voters. Taking as example the "liberal" candidate in polbooks, we need a budget B = 5 to make it overtake the "conservative" candidate in PLTR, while a budget B = 1 is enough in R-PLTR (Figure 1); in polblogs, instead, we are not able to make the "liberal" candidate win in PLTR with budget B = 10, but it is enough a budget B = 5 to make it overtake the "conservative" candidate in R-PLTR (Figure 2).

The results relative to MoV are presented in Figure 3. We can note that, as a general trend, candidates with lower probability of winning, are the most affected by the influence generated by the seed nodes selected by our algorithm both in PLTR and R-PLTR. The "neutral" and "liberal" candidates, respectively last and second last voted, have the higher MoV in polbooks (see Figure 3, on the left), while the "liberal" candidate, which was losing the elections, has the higher MoV in polblogs (see Figure 3, on the right).

Finally, in Figure 4 we present the difference between the MoV calculated by GreedyScore and GreedyIM. The simulations show that our algorithm outperforms GreedyIM, as expected. The only scenario in which our algorithm performs worse is that in which we influence, with low budget, the already winning candidate (see Figure 4, on the left, red lines). The reason why GreedyScore works better than GreedyIM is that it looks for seeds that will influence "critical" voters, i.e., voters on which the influence will have more impact on the global score of the candidates, while GreedyIM just looks for influential voters, independently from their initial opinion.

Conclusions and Future Work

Influencing elections by means of social networks is a significant issue in modern society, and understanding this phenomenon is of crucial importance in order to prevent the integrity of democracy. Our results constitute the first step towards realistic modeling of the use of social influence to control elections as our models take into account that voters might hide their preferences to a controller. In one of our models the election control problem cannot be approximated within any reasonable bound, under some computational complexity hypothesis. For the other model we provide an approximation algorithm that guarantees a constant factor approximation ratio. The results in this paper open several research directions. We plan to study the election control problem in a variant of PLTR where multiple campaigns affect voters' opinions on different candidates. It is also worth to investigate models with uncertainty in other voting systems. Finally, it would be interesting to consider uncertainty models also for the diffusion process, e.g., in robust influence maximization only a probability distribution on the edge's weights is known. Figure 3: The MoV calculated using the presented algorithm for polbooks (left) and polblogs (right), both in PLTR (dashed line) and R-PLTR (solid line), considering as target candidate the "liberal" (blue line), the "conservative" (red line), and the "neutral" (grey line). Values greater than 0 are when our algorithm performs better than the simple Greedy for Influence Maximization.

Algorithm 1 2 :

 12 GreedyScoreRequire:Social graph G = (V, E); Budget B 1: S = ∅; Ĝ = (G, w) Weighted graph Ĝ while |S| ≤ B do 3: v = arg max u∈V \S σ w (S ∪ {u}) -σ w (S)

  We define MoV D , i.e., what we want to maximize, as MoV D (S) := F (ĉ, S) -F (c , S) -(F (c, ∅) -F (c , ∅)) = g -(c , S) + g + (ĉ, S) + ∆,

Figure 1 :

 1 Figure1: Candidates' scores in polbooks in PLTR (left column) and R-PLTR (right column), considering as target candidate the "liberal" (top), the "conservative" (center), and the "neutral" (bottom).

Figure 2 :

 2 Figure 2: Candidates' scores in polblogs in PLTR (left column) and R-PLTR (right column), considering as target candidate the "liberal" (top) and the "conservative" (bottom).

Figure 4 :

 4 Figure 4: Difference between MoV obtained using our greedy algorithm and MoV obtained using the standard greedy algorithm for Influence Maximization problem in polbooks (left) and polblogs (right).Values greater than 0 are when our algorithm performs better than the simple Greedy for Influence Maximization.

The assumption is used in the approximation results, since Influence Maximization problem with exponential (or exponentially small) weights on nodes is an open problem. However, the assumption is realistic: Current techniques to estimate such parameters generate values linear in the number of messages shared by a node.

The increment in margin of victory, instead of just the margin, cannot be negative and gives well defined approximation ratios.

It is still an open question how well the value of σw(S) can be approximated for an influence model with arbitrary node weights.


Thibaud Cochereau

Lucie Bailly
email: lucie.bailly@3sr-grenoble.fr

Laurent Orgéas

Nathalie Henrich Bernardoni

Yohann Robert

Maxime Terrien

Mechanics of human vocal folds layers during finite strains in tension, compression and shear

Keywords: Vocal folds, Mechanical tests, Tension, Shear, Compression

During phonation, human vocal fold tissues are subjected to combined tension, compression and shear loadings modes from small to large finite strains. Their mechanical behaviour is however still not well understood.

Herein, we complete the existing mechanical database of these soft tissues, by characterising, for the first time, the cyclic and finite strains behaviour of the lamina propria and vocalis layers under these loading modes. To minimise the inter or intra-individual variability, particular attention was paid to subject each tissue sample successively to the three loadings. A nonlinear mechanical behaviour is observed for all loading modes : a J-shape strain stiffening in longitudinal tension and transverse compression, albeit far less pronounced in shear, stress accommodation and stress hysteresis whatever the loading mode. In addition, recorded stress levels during longitudinal tension are much higher for the lamina propria than for the vocalis.

Conversely, the responses of the lamina propria and the vocalis in transverse compression as well as transverse and longitudinal shears are of the same orders of magnitude. We also highlight the strain rate sensitivity of the tissues, as well as their anisotropic properties.

Introduction

Human vocal folds are anisotropic soft tissues, comprising two principal layers : the lamina propria, i.e., a loose connective tissue made of collagen and elastin fibers, and the vocalis, composed of skeletal "muscle fibers" (Fig. 1, [START_REF] Hirano | Morphological Structure of the Vocal Cord as a Vibrator and its Variations[END_REF]). The fiber arrangement within these layers exhibits a pronounced alignment along the antero-posterior (or longitudinal) direction e z of the vocal folds (Fig. 1, [START_REF] Hirano | Morphological Structure of the Vocal Cord as a Vibrator and its Variations[END_REF][START_REF] Miri | Microstructural characterization of vocal folds toward a strainenergy model of collagen remodeling[END_REF]). During phonation, vocal folds are deformed due to pulmonary airflow and laryngeal motions, enduring vibrations of various amplitudes, frequencies, and degrees of collision. These multiple configurations imply complex and coupled multiaxial mechanical loadings experienced by the tissue upon finite strains and at various strain rates. These loadings include combined longitudinal tension and compression which are mainly due to laryngeal muscular contractions along e z (Fig. 1), but also transverse compression due to aerodynamic forces and vocal-fold collision along e x , as well as longitudinal and transverse shears due to oscillatory motion along e y and friction stresses between both vocal folds [START_REF] Miri | Mechanical Characterization of Vocal Fold Tissue: A Review Study[END_REF]. These observations are confirmed with finite element simulations of vocal folds oscillations during phonation [START_REF] Gunter | A mechanical model of vocal-fold collision with high spatial and temporal resolution[END_REF][START_REF] Gunter | Modeling mechanical stresses as a factor in the etiology of benign vocal fold lesions[END_REF][START_REF] Vampola | Computer simulation of mucosal waves on vibrating human vocal folds[END_REF][START_REF] Vampola | Simulation of vibration of the human vocal folds[END_REF][START_REF] Tao | Mechanical stress during phonation in a self-oscillating finite-element vocal fold model[END_REF], bringing fruitful semi-quantitative information.

However, current simulations suffer from a lack of experimental data, to use more relevant constitutive mechanical models of vocal tissues.

To investigate the mechanics of vocal-fold tissues, several experimental works have been conducted during the last twenty years [START_REF] Goodyer | Devices and Methods on Analysis of Biomechanical Properties of Laryngeal Tissue and Substitute Materials[END_REF][START_REF] Miri | Mechanical Characterization of Vocal Fold Tissue: A Review Study[END_REF][START_REF] Dion | Functional assessment of the ex vivo vocal folds through biomechanical testing: A review[END_REF].

Most of them focused on the lamina propria response during longitudinal tension. They highlighted the non-linear behaviour of this tissue showing a J-shape stress-strain curve upon loading, and thus, an increasing tangent longitudinal modulus E t z from 10 kPa to 2000 kPa [START_REF] Kelleher | Optical measurements of vocal fold tensile properties: Implications for phonatory mechanics[END_REF][START_REF] Kelleher | Empirical measurements of biomechanical anisotropy of the human vocal fold lamina propria[END_REF][START_REF] Chan | Relative Contributions of Collagen and Elastin to Elasticity of the Vocal Fold Under Tension[END_REF][START_REF] Min | Stress-strain response of the human vocal ligament[END_REF][START_REF] Kelleher | Spatially varying properties of the vocal ligament contribute to its eigenfrequency response[END_REF]. Viscoelastic properties of this layer were also investigated using either standard shear Dynamic Mechanical Analysis (DMA), i.e., within the linear regime [START_REF] Chan | Viscoelastic shear properties of human vocal fold mucosa: measurement methodology and empirical results[END_REF][START_REF] Chan | A simple-shear rheometer for linear viscoelastic characterization of vocal fold tissues at phonatory frequencies[END_REF][START_REF] Goodyer | In vivo measurement of the elastic properties of the human vocal fold[END_REF][START_REF] Rohlfs | The anisotropic nature of the human vocal fold: an ex vivo study[END_REF], or more recently using Large Amplitude Oscillatory Shear (LAOS) [START_REF] Chan | Nonlinear viscoelastic characterization of human vocal fold tissues under largeamplitude oscillatory shear (laos)[END_REF]. These works allowed to characterise the shear storage G and loss G moduli (DMA) of the lamina propria, as well as its cyclic and finite strains shear behaviour (LAOS) within the (x, y) plane. Several conclusions can be drawn therefrom. Firstly, G and G (i) are of the same order of magnitude and exhibit a non-linear shear rate stiffening, (ii) vary within a wide range of values (from 1 Pa to 10 kPa), that are much lower than those recorded for E t z . Point (i) proves that viscous effects play a key role on the mechanics of the lamina propria. Point (ii) emphasises the anisotropy of the lamina propria behaviour, which is directly induced by its structural anisotropy [START_REF] Bailly | 3d multiscale imaging of human vocal folds using synchrotron X-ray microtomography in phase retrieval mode[END_REF]. Secondly, the lamina propria cyclic shear stress-strain curves also exhibited a J-shape, with an increase of the strain stiffening above a shear strain around 0.5 [START_REF] Chan | Nonlinear viscoelastic characterization of human vocal fold tissues under largeamplitude oscillatory shear (laos)[END_REF].

Despite this important database, there are still some issues to be tackled to understand and model the mechanics of human vocal folds. Among them is the difficulty to analyse experimental results due to the large variability of the mechanical response between subjects, and within the tissues themselves [START_REF] Chan | Relative Contributions of Collagen and Elastin to Elasticity of the Vocal Fold Under Tension[END_REF][START_REF] Chan | Viscoelastic shear properties of human vocal fold mucosa: measurement methodology and empirical results[END_REF][START_REF] Rohlfs | The anisotropic nature of the human vocal fold: an ex vivo study[END_REF], as for other soft living materials [START_REF] Cavinato | Does the knowledge of the local thickness of human ascending thoracic aneurysm walls improve their mechanical analysis[END_REF]. It is thus challenging to compare data obtained with different mechanical loadings, e.g., tension and shear. In addition, the mechanics of the lamina propria during transverse compression has never been studied so far. This constitutes a crucial lack in current knowledge, keeping in mind that the quality of contact between vocal folds is a key factor in voice quality, and that highimpact transverse compressive stresses are believed to generate common lesions in the lamina propria after a phonotrauma [START_REF] Hantzakos | Exudative lesions of Reinke's space: a terminology proposal[END_REF][START_REF] Lagier | Approche expérimentale de la collision entre les plis vocaux en phonation et du phonotraumatisme: Études in vivo et sur larynx humains excisés[END_REF]. Finally, the mechanics of the vocalis has been often discarded up to now, although being a major vocal-fold sublayer used to tune the phonation process, in its active but also passive state.

Therefore, this study aims to provide a new mechanical dataset of human vocal-fold tissues, subjected to a series of physiological loadings, i.e., longitudinal tension, transverse compression as well as longitudinal and transverse shear. These testing conditions were achieved sequentially on each sample, thereby minimising inter-sample variability. We studied and compared the finite strains mechanical responses of both upper layers, including epithelium and lamina propria (Fig. 1), to those of the vocalis muscle for each loading mode. Finally, we quantified the strain rate sensitivity of these tissues, as well as their mechanical anisotropy.

Materials and Methods

Vocal folds

Experiments were carried out with 4 healthy human larynges, noted Table 1: Origin of the tested larynges.

L i , i ∈ [1, 2,

Experimental protocol

We designed a protocol to characterise the finite strains mechanics of the vocalis and upper layers (lamina propria + epithelium) under tension, compression and shear, while minimising the inter and intra-individual variability.

Hygro-mechanical set-up

Mechanical tests were conducted at proper hygrometric conditions to prevent the tissues from air drying [START_REF] Nicolle | Dehydration effect on the mechanical behaviour of biological soft tissues : Observations on kidney tissues[END_REF], using a chamber (Fig. 2

Testing protocol

• Tensile tests were first carried out with vocal folds L i -F j (Fig. 2(b)), the gauge length 0 and cross-section S 0 of which are reported in Table 2. Tests were performed along e z , i.e., the main fiber orientation. The cell force f signal and the LVDT displacement δ were used to estimate the first Piola-Kirchoff stress P zz = f /S 0 , as well as the Hencky tensile strain ε zz = ln(1 + δ/ 0 ). Each sample was subjected to 10 load-unload cycles at a strain rate

| εzz | = | δ/ 0 | ≈ 10 -3 s -1 , up
to a moderate tensile strain ε max zz = 0.1 to restrain sample damage.

• Samples were then unmounted, and their upper layers (further la-belled L i -LP j ) were separated from the vocalis (L i -M j ). Epithelium was left intact as a remaining part of the L i -LP j layer. Care was taken to preserve cartilages parts on both layers. Then, each sample was again subjected to tension loading along e z following the aforementioned procedure (see Table 2 for their dimensions).

• Therewith, samples L i -LP j and L i -M j (i = 3, 4) were released from their cartilaginous ends and resized in smaller parallelepiped samples in order to fit compression and shear plates, as described in Fig. S2(c) (see Table 2, "compression" column for their adjusted dimensions). They were then subjected to compression along e x (Fig. 2 tance between platens or clamps (Fig. 2(b)). The mean initial cross section S 0 and its standard deviation were estimated optically from the width and the thickness profiles of the samples once put onto a flat surface.

Results

General trends in tension

Tensile responses of the vocal folds and their sublayers along e z are reported in Fig. 3 for the first cycle, together with the evolution of the longitudinal tangent moduli E t z = dP zz /dε zz with ε zz (for the first loading only).

Variability -Fig. 3 first emphasises a large scattering of the mechanical responses. For instance, at ε zz ≈ 0.09, the ratio of maximal and minimal stresses registered in the case of the L i -F j samples rises up to 5. This wellknown inter-individual variability is ascribed to tissue histological singularities of each donor, which depends on age, gender, tobacco smoking profile [START_REF] Chan | Viscoelastic shear properties of human vocal fold mucosa: measurement methodology and empirical results[END_REF][START_REF] Chan | Effect of postmortem changes and freezing on the viscoelastic properties of vocal fold tissues[END_REF][START_REF] Chan | Relative Contributions of Collagen and Elastin to Elasticity of the Vocal Fold Under Tension[END_REF]. Conversely, note that the intra-individual variability is much less marked : the ratio of maximal to minimal stresses at ε zz ≈ 0.09 is only 1.3 for left and right vocal-fold samples. Similar conclusions are drawn for upper layers L i -LP j and vocalis L i -M j .

Shape of stress-strain curves and corresponding stiffness -Whatever the sample, stress-strain curves exhibit non-linear responses with a J-shape strainhardening (Fig. 3, left) and a strain hardening of tangent moduli (right).

These trends are related to the recruitment and reorientation of wavy fibers during tension [START_REF] Min | Stress-strain response of the human vocal ligament[END_REF][START_REF] Gasser | Hyperelastic modelling of arterial layers with distributed collagen fibre orientations[END_REF][START_REF] Fratzl | Fibrillar Structure and Mechanical Properties of Collagen[END_REF]. They are less marked for vocalis samples, the muscle fibers being straighter than the collagen/elastin fibers of the upper layers at rest (Fig. 1, [START_REF] Bailly | 3d multiscale imaging of human vocal folds using synchrotron X-ray microtomography in phase retrieval mode[END_REF]). In addition, reported stress-strain curves exhibit stress hysteresis with a non-negligible residual strain after unloading, which may be ascribed to viscoelastic effects together with structure rearrangements.

Comparison between sublayers -Fig. 3 also proves that stress levels in upper layers are much higher than those recorded for the vocalis. For example, at ε zz = 0.1, nominal stresses P zz vary from 14 to 50 kPa, from 8 kPa to more than 100kPa, and from 0.5 kPa to 28 kPa for vocal folds, upper layers, and vocalis samples, respectively. A similar conclusion is drawn for the tangent moduli E t z (Fig. 3).

Mechanics in tension, compression and shear for single samples

To get rid of the aforementioned inter or intra-individual variablility, focus is now made on samples L 3 -LP 2 , L 4 -LP 2 , L 3 -M 2 and L 4 -M 2 , subjected to the protocol purposely designed. Despite this procedure, some stress scatterings remain due to sample dimensions (Table 2): in Figs. Shape of stress-strain curves -Compared to tension along e z , the compression along e x yields to similar J-shape stress-strain curves during the first loading. However, during unloading, compression stress-strain curves exhibit a marked hysteresis with higher residual strains. In addition, stress levels of upper layers are of the same order of magnitude than those of the vocalis, which is also different to what is observed in tension. By contrast, stress-strain curves obtained in shear do not exhibit a J-shape, but a practically constant strain hardening. Note that the apparent strain softening produced at the end of the load (notably for the vocalis) is probably due to experimental artefacts, such as sample rocking. In addition, despite a slightly stiffer response for the vocalis compared to the upper layers, orders of magnitude of stress levels generated within both sublayers are comparable up to 0.2 shear strain. Lastly, the shear stress hysteresis as well as the residual shear strain are limited.

Effect of cycling -Whatever the samples, repeating load-unload sequences yields to progressive (i) decrease of maximal stresses, (ii) decrease of the stress hysteresis, (iii) increase of the residual strains. These evolution are commonly observed while cycling soft tissues [START_REF] Remache | The effects of cyclic tensile and stress-relaxation tests on porcine skin[END_REF] and consistent with previous studies [START_REF] Zhang | Modeling of the transient responses of the vocal fold lamina propria[END_REF][START_REF] Kelleher | The anisotropic hyperelastic biomechanical response of the vocal ligament and implications for frequency regulation: A case study[END_REF][START_REF] Chan | Relative Contributions of Collagen and Elastin to Elasticity of the Vocal Fold Under Tension[END_REF]. For both sublayers, these effects are limited in shear (Figs. 4 and5), but pronounced in tension and compression.

Effect of strain rate -Fig. 6(a) shows typical stress-strain curves obtained

with sample L 4 -LP 2 compressed at | εxx | ≈ 10 -3 s -1 and | εxx | ≈ 10 -2 s -1 .
As expected, the tissue viscoelasticity yields to a moderate to strong increase of stress levels and hysteresis with the strain rate. Fig. 6(b) displays the compression stress ratio P 2 xx /P 1 xx of the 8 tested samples with the compression strain during the first loading, where P 1 xx (resp. P 2 xx ) is the stress at 10 -3 s -1 (resp. 10 -2 s -1 ) : this ratio ranges within 1.1 and 3.3. For most of samples, it exhibits a slight increase during compression. Furthermore, for the same vocal fold (at fixed i and j-values), the ratios of samples L i -LP j and L i -M j follow roughly close evolutions.

Anisotropy -The stress-strain response of sample L 3 -LP 1 in shear parallel to the (e y , e x ) and to the (e z , e x ) planes is presented in Fig. 6(c). For both shear directions, the shape of the curve is similar but stresses are about twice higher in the (e y , e x ) plane, emphasising a marked anisotropy. This feature is confirmed in Fig. 6

Discussion and concluding remarks

This study provides original biomechanical data (20 samples) for excised human vocal folds, their upper layers and the vocalis, by completing the knowledge of their finite strains mechanics in tension, compression and shear.

With respect to literature data, the database conjures up the following comments. In tension, the orders of magnitude of the longitudinal tangent modulus E t z of the upper layers are in agreement with previous ex vivo data. For instance, in the linear regime, Min et al. [START_REF] Min | Stress-strain response of the human vocal ligament[END_REF] gave values around 20-50 kPa for the lamina propria. Other values range between 10 and 600 kPa for the isolated "cover" (i.e., epithelium + lamina propria superficial layer) [START_REF] Chan | Relative Contributions of Collagen and Elastin to Elasticity of the Vocal Fold Under Tension[END_REF][START_REF] Kelleher | The anisotropic hyperelastic biomechanical response of the vocal ligament and implications for frequency regulation: A case study[END_REF][START_REF] Kelleher | Empirical measurements of biomechanical anisotropy of the human vocal fold lamina propria[END_REF][START_REF] Kelleher | Optical measurements of vocal fold tensile properties: Implications for phonatory mechanics[END_REF][START_REF] Miri | Mechanical Characterization of Vocal Fold Tissue: A Review Study[END_REF], and between 10 to 110 kPa for the "vocal ligament" (i.e., lamina propria mid and deep layers) [START_REF] Chan | Relative Contributions of Collagen and Elastin to Elasticity of the Vocal Fold Under Tension[END_REF][START_REF] Kelleher | The anisotropic hyperelastic biomechanical response of the vocal ligament and implications for frequency regulation: A case study[END_REF][START_REF] Kelleher | Empirical measurements of biomechanical anisotropy of the human vocal fold lamina propria[END_REF][START_REF] Kelleher | Optical measurements of vocal fold tensile properties: Implications for phonatory mechanics[END_REF]. For tensile strains above 0.4, the range is even wider, from 20 to 500 kPa for lamina propria [START_REF] Min | Stress-strain response of the human vocal ligament[END_REF], up to 1850 kPa for cover [START_REF] Chan | Relative Contributions of Collagen and Elastin to Elasticity of the Vocal Fold Under Tension[END_REF] and 3300 kPa for ligament. The sources of such a scattering are mainly related to intra/inter-individual variability. This was here again emphasised and conducted us to design a procedure to better compare experimental results (tension, compression and shear). In addition, to our knowledge, tensile data recorded for the human vocalis are original and cannot be compared with other literature data. Alternatively, close stress levels can be found on other skeletal muscles stretched along the main fiber direction such as Longissimus dorsi samples (10 kPa stress at a strain of 0.1), albeit taken from fresh pig tissues [START_REF] Takaza | The anisotropic mechanical behaviour of passive skeletal muscle tissue subjected to large tensile strain[END_REF]. Furthermore, our shear data showed that the tangent shear moduli of the upper layers range from 0.36 to 2.3 kPa and from 0.25 to 2.5 kPa in the longitudinal and transverse direction, respectively. These values are similar to those obtained while shearing vocal-fold covers (without specifying the shearing plane), i.e., between 1 Pa to 1 kPa [START_REF] Chan | A simple-shear rheometer for linear viscoelastic characterization of vocal fold tissues at phonatory frequencies[END_REF]. Our estimates are also consistent with apparent elastic properties recorded with a linear skin rheometer (LSR) with vocal fold and sublayer samples [START_REF] Rohlfs | The anisotropic nature of the human vocal fold: an ex vivo study[END_REF].

In this study, the anisotropy of the apparent shear moduli was emphasised but the shear anisotropy ratio remained below 1 (0.5-0.75) at small apparent strains, whereas ours are such that 1 < G t yx /G t zx < 3 within a larger strain range. Any further comparison is limited by uncertainties related to the assumptions stated both for the sample dimensions and the stress-strain state homogeneity using the LSR technique. Lastly, although transverse compression is a key mechanical loading during voice production [START_REF] Tao | Mechanical stress during phonation in a self-oscillating finite-element vocal fold model[END_REF][START_REF] Miri | Mechanical Characterization of Vocal Fold Tissue: A Review Study[END_REF][START_REF] Vampola | Simulation of vibration of the human vocal folds[END_REF], compression experiments on vocal folds have not been reported so far. Few other biological materials have been characterised in compression, this loading being usually preferred for very soft tissues, the shear or tensile behaviour of which are tricky to characterise [START_REF] Miller | Method of testing very soft biological tissues in compression[END_REF][START_REF] Morriss | Compression testing of very soft biological tissues using semi-confined configuration : a word of caution[END_REF]. For instance, results can be found on adipose porcine tissue [START_REF] Comley | The compressive response of porcine adipose tissue from low to high strain rate[END_REF], lung tissue [START_REF] Andrikakou | On the behaviour of lung tissue under tension and compression[END_REF] or muscles [START_REF] Pietsch | Anisotropic Compressive Properties of Passive Porcine Muscle Tissue[END_REF][START_REF] Ehret | On the anisotropy of skeletal muscle tissue under compression[END_REF]: they emphasise non-linear properties similar to the trends highlighted here.

The present database shows that vocal-fold layers behave as many other soft living tissues subjected to finite strains, i.e., with a non-linear viscoelastic and anisotropic behaviour exhibiting strain hardening and strain rate sensitivity, stress hysteresis and accommodation. These features are connected both to their inner gel-like ground substances and their orientated fibrous architectures which reorient, rearrange and deform differently with the loading mode and direction. In addition, by minimising the inter or intra-individual variability, the proposed experimental procedure allowed a quantitative comparison of results. Thus, important differences are emphasised for the aforementioned mechanical features as a function of the loading modes. The mechanical role of the sublayers on the vocal folds mechanics is also better established. For instance, our data prove that the passive mechanical behaviour of the vocalis in tension is minor with respect to that of the upper layers. By contrast, stress levels achieved in compression and shear are close for both the upper layers and the vocalis. In addition, it is interesting to note that stress levels obtained in compression and shear are much (resp. moderately) lower than those obtained in tension for the upper layers (resp. the vocalis). Hence, by completing the existing database, these results constitutes a quantitative information for the validation of biomechanical models of phonation. It should also be completed, e.g., by further scrutinising the strain rate sensitivity at

  Fig.1(b), and pictured in Supplementary Figs.S1(a) and S2(a): they were made of all sublayers from their epithelium to the vocalis (Fig.1), and noted L i -F j (j = 1 and j = 2 standing for left and right vocal folds of larynx L i , respectively). Finally, samples L 3 -F 1 and L 4 -F 1 were cut in half along the plane (e x , e z ), as shown in Supplementary Fig.S2(b). One half was dedicated to histological analyses, following the protocol detailed in Bailly et al., 2018[START_REF] Bailly | 3d multiscale imaging of human vocal folds using synchrotron X-ray microtomography in phase retrieval mode[END_REF]. The second half was dedicated to mechanical testing.

  (a)) in which a saturated air flow (≈ 95 -100 %RH) was regulated with a humidifier (Fisher and Paykel HC150). We also used a tension-compression micro-press inserted inside the chamber and designed for soft samples (load cell 5 N, relative displacement between crossheads measured with a LVDT sensor) [27, 20, 28, 25, 2]. For simple tensile tests, specially designed knurled clamps (26 mm width, 7 mm height) were used to facilitate the sample positioning and restrain its slippage (Fig. 2(b)). For simple compression tests, compression platens were hydrated by a film of Phosphate-buffered saline solution, avoiding friction (Fig. 2(b)). For simple shear tests, plates (10 mm length and width) were coated with sand paper to restrain sample slippage (Fig. 2(b)).

  (b)). During the tests, compression stress P xx = f /S 0 and compression strain ε xx = ln(1 + δ/ 0 ) were recorded. Samples were subjected to 10 load-unload cycles up to ε min xx = -0.2. This procedure was carried out at two strain rates, | εxx | = | δ/ 0 | ≈ 10 -3 s -1 and 10 -2 s -1 , respectively. • Finally, we conducted two consecutive shear tests with the same samples along two different directions, "longitudinal" plane (e z , e x ) and "transversal" plane (e y , e x ), respectively. During the tests, shear stress P zx = f /S 0 (resp. P yx = f /S 0 ) was measured as a function of shear strain γ zx = δ/ 0 (resp. γ yx = δ/ 0 ), while subjecting samples to 10 load-unload cycles up to γ max zx = 0.6 (resp. γ max yx = 0.6) at a shear rate | γ| = | δ/ 0 | ≈ 10 -3 s -1

4 and 5

 45 presented hereafter, they have been highlighted with gray corridors surrounding nominal values of stresses. The first figure gives stress-strain curves after subjecting samples L 3 -LP 2 and L 3 -M 2 to 10 load-unload cycles in tension, compression and shear. The second one reports similar data for samples L 4 -LP 2 and L 4 -M 2 .

Table 2 :

 2 . Sample dimensions used to determine stresses and strains. 0 is the initial dis-

			Sample gauge dimensions
			Tension	Compression		Shear
	Name	0 (mm) S † 0 (mm 2 )	0 (mm) S † 0 (mm 2 )	0 (mm) S † 0 (mm 2 )
	L 1 -F	10.1	28.9±2.4	-	-	-	-
	L 1 -LP	15	8.9±4.8	-	-	-	-
	L 1 -M 1	7	9.8±4.2	-	-	-	-
	L 1 -F	10.3	40.8±6.1	-	-	-	-
	L 1 -LP	8.5	5.4±3.6	-	-	-	-
	L 1 -M 2	7.2	14.4±5.8	-	-	-	-
	L 2 -F	16.8	49.2±7.2	-	-	-	-
	L 2 -LP	18	21.3±7.6	-	-	-	-
	L 2 -M 1	17.8	24.3±9.8	-	-	-	-
	L 2 -F	19.8	38.6±7.2	-	-	-	-
	L 2 -LP	22.3	13.2±7.1	-	-	-	-
	L 2 -M 2	18.3	19.9±9.3	-	-	-	-
	L 3 -F	14.2	39.0±11.5	-	-	-	-
	L 3 -LP	10	7.4±2.9	1.5	80.0±0.7	1.0	68.5±4.7
	L 3 -M 1	10	8.8±4.4	1.9	91.9±0.8	1.3	99.0±9.5
	L 3 -F	17.8	82.3±20.2	-	-	-	-
	L 3 -LP	15.7	14.7±4.7	1.1	74.9±5.8	0.9	78.9±0.6
	L 3 -M 2	11.5	29.3±10.1	2.6	120.1±15.8	2.1	78.0±7.1
	L 4 -LP	15.2	5.8±4.5	0.9	44.8±1.6	0.6	44.6±4.1
	L 4 -M 1	15.7	11.9±4.0	1.5	81.7±1.2	1.0	84.4±0.3
	L 4 -LP	14	11.7±5.4	1.3	88.6±0.7	1.3	99.0±9.5
	L 4 -M 2	15.3	14.4±5.6	2.2	93.7±0.9	2.1	72.9±11.9

Acknowledgements

This work was supported by the LabEx Tec 21 (Investissements d'Avenir -grant agreement n ˚ANR-11-LABX-0030), the INSIS PEPS 2016 Micropli (CNRS) and the ANR MicroVoice n ˚ANR-17-CE19-0015-01. We would like to thank Philippe Masson, Alberto Terzolo, Anne McLeer and Philippe Chaffanjon for their helpful assistance.

Conflict of interest statement

The authors declare no conflict of interest.