Paul Gassiat
email: gassiat@ceremade.dauphine.fr

A STOCHASTIC HAMILTON-JACOBI EQUATION WITH INFINITE SPEED OF PROPAGATION

We give an example of a stochastic Hamilton-Jacobi equation du = H(Du)dξ which has an infinite speed of propagation as soon as the driving signal ξ is not of bounded variation.

introduction

An important feature of (deterministic) Hamilton-Jacobi equations (1.1)

∂ t u = H(Du) on (0, T ) × R N
is the so-called finite speed of propagation : assuming for instance that H : R N → R is C-Lipschitz, then if u 1 and u 2 are two (viscosity) solutions of (1.1), one has

(1.2) u 1 (0, •) = u 2 (0, •) on B(R) ⇒ ∀t ≥ 0, u 1 (t, •) = u 2 (t, •) on B(R -Ct)
where by B(R) we mean the ball of radius R centered at 0. In this note, we are interested in Hamilton-Jacobi equations with rough time dependence of the form

(1.3) ∂ t u = H(Du) ξ(t) on (0, T ) × R N ,
where ξ is only assumed to be continuous. Of course, the above equation only makes classical (viscosity) sense for ξ in C 1 , but Lions and Souganidis [START_REF] Lions | Fully nonlinear stochastic partial differential equations: non-smooth equations and applications[END_REF] have shown that if H is the difference of two convex functions, the solution map can be extended continuously (with respect to supremum norm) to any continuous ξ. (In typical applications, one wants to take ξ as the realization of a random process such as Brownian motion).

In fact, the Lions-Souganidis theory also gives the following result : if

H = H 1 -H 2 where H 1 , H 2 are convex, C-Lipschitz, with H 1 (0) = H 2 (0) = 0, then for any constant A, u(0, •) ≡ A on B(R) ⇒ u(t, •) ≡ A on B(R(t)) where R(t) = R -C(max s∈[0,t] ξ(s) -min s∈[0,t] ξ(s)).
However this does not imply a finite speed of propagation for (1.3) for arbitrary initial conditions, and a natural question (as mentioned in lecture notes by Souganidis [START_REF] Souganidis | Fully nonlinear first-and second-order stochastic partial differential equations[END_REF]) is to know whether a property analogous to (1.2) holds in that case. The purpose of this note is to show that in general it does not : we present an example of an H such that if the total variation of ξ on [0, T ] is strictly greater than R, one may find initial conditions u1 0 , u 2 0 which coincide on B(R), but such that for the associated solutions u 1 and u 2 , one has u 1 (T, 0) = u 2 (T, 0).

For instance, if ξ is a (realization of a) Brownian motion, then (almost surely), one may find initial conditions coinciding on balls of arbitrary large radii, but such that u (t, 0) = u 2 (t, 0) for all t > 0.

It should be noted that the Hamiltonian H in our example is not convex (or concave). When H is convex, some of the oscillations of the path cancel out at the PDE level 1 , so that one cannot hope for simple bounds such as (2.2) below. Whether one has finite speed of propagation in this case remains an open question.

main result and proof

We fix T > 0 and denote

P = {(t 0 , . . . , t n ), 0 = t 0 ≤ t 1 ≤ . . . ≤ t n = T } the set of partitions of [0, T ]. Recall that the total variation of a continuous path ξ : [0, T ] → R is defined by V 0,T (ξ) = sup (t 0 ,...,tn)∈P n-1 i=0 |ξ(t i+1 ) -ξ(t i )| .
Our main result is then :

Theorem 1. Given ξ ∈ C([0, T ]), let u : [0, T ] × R 2 → R be the viscosity solution of (2.1) ∂ t u = (|∂ x u| -|∂ y u|) ξ(t) on (0, T ) × R 2
with initial condition u(0, x, y) = |x -y| + Θ(x, y) where Θ ≥ 0 is such that Θ(x, y) ≥ 1 if min x, y ≥ R.

One then has the estimate

(2.2) u(T, 0, 0) ≥ sup (t 0 ,...,tn)∈P n-1 j=0 |ξ(t j+1 ) -ξ(t j )| n - R n + ∧ 1.
In particular, u(T, 0, 0) > 0 as soon as V 0,T (ξ) > R.

Note that since |x -y| is a stationary solution of (2.1), the claims from the introduction about the speed of propagation follow.

The proof of Theorem 1 is based on the differential game associated to (2.1). Informally, the system is constituted of a pair (x, y) and the two players take turn controlling x or y depending on the sign of ξ, with speed up to | ξ|. The minimizing player wants x and y to be as close as possible to each other, while keeping them smaller than R. The idea is then that if the minimizing player keeps y and x stuck together, the maximizing player can lead x and y to be greater than R as long as V 0,T (ξ) > R.

Proof of Theorem 1. By approximation we can consider ξ ∈ C 1 , and in fact we consider the backward equation :

(2.3) -∂ t v = (|∂ x v| -|∂ y v|) ξ(t), v(T, x, y) = |x -y| + Θ(x, y).
We then need a lower bound on v(0, 0, 0). Note that

(|∂ x v| -|∂ y v|) ξ(t) = sup |a|≤1 inf |b|≤1 ξ+ (t) (a∂ x u + b∂ y u) + ξ-(t) (a∂ y u + b∂ s u) ,
so that by classical results (e.g. [START_REF] Evans | Differential games and representation formulas for solutions of Hamilton-Jacobi-Isaacs equations[END_REF]) one has the representation

(2.4) v(0, 0, 0) = sup δ(•)∈∆ inf β∈U J(δ(β), β),
where U is the set of controls (measurable functions from [0, T ] to [-1, 1]) and ∆ the set of progressive strategies (i.e. maps δ :

U → U such that if β = β a.e. on [0, t], then δ(β)(t) = δ(β )(t)).
Here for α, β ∈ U, the payoff is defined by

J(α, β) = |x α,β (T ) -y α,β (T )| + Θ(x α,β (T ), y α,β (T ))
where

x α,β (0) = y α,β (0) = 0, ẋα,β (s) = ξ+ (s)α(s)+ ξ-(s)β(s), ẏα,β (s) = ξ-(s)α(s)+ ξ+ (s)β(s).

Assume v(0, 0, 0) < 1 (otherwise there is nothing to prove) and fix ε ∈ (0, 1) such that v(0, 0, 0) < ε. Consider the strategy δ ε for the maximizing player defined as follow : for β ∈ U, let

τ β ε = inf t ≥ 0, |x 1,β (t) -y 1,β (t)| ≥ ε , and then δ ε (β)(t) = 1, t < τ β ε β(t), t ≥ τ β ε .
In other words, the maximizing player moves to the right at maximal speed, until the time when |x -y| = ε, at which point he moves in a way such that x and y stay at distance ε. Now by (2.4), there exists β ∈ U with J(δ ε (β), β) < ε. Clearly for the corresponding trajectories x(•), y(•), this means that |x(T ) -y(T )| < ε, and by definition of α ε this implies |x(t) -y(t)| ≤ ε for t ∈ [0, T ]. We now fix (t 0 , . . . , t n ) ∈ P and prove by induction that for i = 0, . . . , n,

min{x(t i ), y(t i )} ≥ i-1 j=0 |ξ(t j+1 ) -ξ(t j )| -iε.
Indeed, if it is true for some index i, then assuming that for instance ξ(t i+1 ) -ξ(t i ) ≥ 0, one has

x(t i+1 ) = x(t i ) + t i+1 t i ξ+ (s)ds - t i+1 t i β(s) ξ-(s)ds ≥ x(t i ) + ξ(t i+1 ) -ξ(t i ) ≥ i j=0
|ξ(t j+1 ) -ξ(t j )| -iε and since y(t i+1 ) ≥ x(t i+1 )-ε, one also has y(t i+1 ) ≥ i j=0 |ξ(t j+1 ) -ξ(t j )|-(i+1)ε. The case when ξ(t i+1 ) -ξ(t i ) ≤ 0 is similar.

Since J(α ε (β), β) ≤ 1, one must necessarily have min{x(T ), y(T )} ≤ R, so that

ε ≥ 1 n n j=0 |ξ(t j+1 ) -ξ(t j )| -R .
Letting ε → v(0, 0, 0) and taking the supremum over P on the r.h.s. we obtain (2.2).

for example : for δ ≥ 0, S H (δ) • S -H (δ) • S H (δ) = S H (δ), where S H , S -H are the semigroups associated to H, -H.


Thomas Forissier

Context effect in climatic seasons and moon observation conception in the French West Indies

), a shift is observable between the context of learners and the context of the teacher or the discipline, this article focuses on the idea of the effects of educational contexts (Leurette and Author, 2009) closely linked to learning objectives (climate and astronomical in this text, but may also be ecological, geographical or geological). This idea, very close to epistemological (Bachelard,

2) Rationale

The aim of this article is to estimate the scientific conceptions of first-year university students from Guadeloupe about two observations: the shape of the moon, especially its orientation relative to the vertical, and the climatic characteristics of the seasons. This choice is justified by three common characteristics:

• They correspond to direct and frequent observations of nature. They do not require complex equipment or protocol. They are not rare, and everyone in inter-tropical zone, is confronted daily with the weather (precipitations and temperature) and very often with observation of the moon. • They are treated in science courses in French secondary school, in life and earth sciences for seasons, and physical and chemistry for the observation of the moon. These are national programs and textbooks are the same in the French West Indies and in the rest of the country. • Many representations of the temperate seasons and the vertical moon are used in Caribbean zone. They are related to the arts (literature, cinema, music...) and to various symbols (drawing, for example, on the agendas of the moon). For these two examples, a contradiction exists between the first point, linked to direct and local observation, and the two others correspond to observations of temperate zone. This article aims to estimate the relative impact of these factors on conceptions [START_REF] Giordan | Les origines du savoir[END_REF]) of students at the end of their secondary school. In other words, our goal is to observe, on a representative sample of students (first year of science university), if their description of the temperate seasons is more accurate than the seasons of the West Indies, and if their conceptions are related with simple observation of nature. We are particularly concerned in students who will follow a university course for science because we start from the premise that they are no less influenced by the science courses in their designs than other students. In addition, the first goal of science education in secondary schools is defined in the official instructions (Ministère de l'éducation nationale, de la jeunesse et de la vie associative, 2008):

"Following their studies in college, students must have built the first comprehensive and coherent representation of the world in which he lives. It must provide some simple but consistent response to questions: "How is the world I live? "" What is my place? "" What are the individual and collective responsibilities?"

3) Methods

The sample consists of 124 first year (Licence 1) Science students. This first year is common for students intending to pursue studies in mathematics, physics, chemistry, biology or geology. The questionnaire was filled in 15 minutes in university context (amphitheatre). The first multiple choice questions analyzed here ask to characterize the climatic seasons of 2 towns, one in Guadeloupe, and the other in France. The second question asks to choose a photography (see on the right) that could have been taken in Guadeloupe (it is stated that the top of the photo corresponds to the vertical). Only the second picture corresponds to an observation made in tropical latitude, it is the expected answer. The first picture corresponds to a usual observation in the temperate zone and the third is rotated to appear upright. On pie diagrams, the answers expected or considered valid appear in shades of green, non -responses in blue, the others red or orange. Statistics analysis and significant results (5% Khi2 possibly with Yates correction) have been found.

4) Results

The descriptions of seasons completed by the students of science in first year university in Guadeloupe oppose the winter and summer in one part to the "Carême" and "hivernage" on the other. For the observable seasons, no answer expected have been found (hot and humid for hivernage, carême cold and dry), 19% or 30% valid response (wet winter, dry Lent) and between 70% and 80% of unexpected answers. Summer and winter are described correctly in 90% of cases. These response profiles are highly dependent pairs (p <1 ‰). A correlation (p <0.05) between the responses and expected studies for the next year is noted: valid responses are most often given by students intending to pursue MIPC (Math, Computer Science, Physics, Chemistry) than by those intending to pursue in Natural Sciences.

Of the three photographies, only the second was taken in Guadeloupe. Only 7% of students have only checked this photograph, 10% have checked photograph 2 and another one. The most common answers (71% in total) are those excluded photograph 2. A correspondence exists (p <0.05) between the validity of those responses about the direction of the moon and the months cited to describe the winter.

5) Conclusions and Implications

The photograph of the moon taken in Guadeloupe is chosen by only 17% of first year science students. Less than 10% have chosen this photography only. Night falling to 18.30 in Guadeloupe, we exclude hypothesis that students never look at the moon. Then, the question is what they see when they watch the moon. An interpretation taking into account the relationship with reality and the observable can design the Umwelt (Uexküll 1965) of students. Their representation of the moon being built from models and observations when the moon is vertical or slightly tilted: international models used in teaching the phases of the moon, models such as daily diaries, meteorology or cultural product in temperate zones (movies, children's books, various illustrations). First-year science students describe the temperate seasons much better than seasons of the place they live both in terms of periods of the year (month quoted) and climatic characteristics. The seasons and their roles in the occupation of ecosystems are a part of national school programs (for 11-12 years old pupils) without specifying which seasons are in question. But the occupation of the ecosystems is weakly explained by the seasons in Caribbean zone, compared to ecology data between tropical rain forests to dry forests and mangrove areas (salinity).

Here we seem to face a kind of inverted obstacle in the epistemological sense. It is not the naive observation of nature that makes it more difficult to understand scientific concepts but universal selection of content (examples, models, order of ideas) that explains science taught imperfectly observable in an individual educational setting.

  Photo 2 Photo 1 et 2 Photo 2 et 3 Photo 1 Photo 3 Photo 1 et 3, NR


Volorpore Cone

Quiae Perrum

Piditium

To answer your question it is important to remember what is innovation today. To be competitive, a company today can't only rely on improving its products and services. It has to propose new definitions of things. Everybody is aware of this when it comes to 'mobile phones' that have regularly changed their own identity in the last decades, becoming 'smart phones'.

This is also true in other industries: a company will propose automobiles that are not automobiles (electric cars, autonomous cars, etc.), bikes that are not bikes (see Velib in France), vacuum cleaners that are not vacuum cleaners. This new design regime has been unfolding since the mid 1990s. It calls for new methods or processes that are far different from the ones of the R&D departments of the 20 th century.

In a sense this is an industrial revolution. C-K theory is born from the crisis of traditional innovation management: let's remember what was an engineering department in the 1990s, for instance in the automotive industry: these were 'white-collar factories' where 10,000 engineers and technicians saw their creative energy 'fixed' in the refinement of existing products and services and not really in a position to invent the disruptions and breakthroughs that ensure a sustainable future for the company and for society.

In the 1990s, when this regime begins to emerge, practitioners and researchers are confronted by an enigma: how can one account for the paradox according to which design results in something whose identity is different from everything that existed before, yet it is made of building blocks that existed before?

Resolving the enigma was an area of critical competition for scientists. The issue was to propose a theory that accounts for the design of new identities, new definitions of objects, or, more generally, that account for the 'generation' of the new out of the 'known'. This theory should, of course, present all the features of a 'good theory', i.e., rigour, consistency of the reasoning, capacity to account for facts, capacity to enlighten original phenomena. Such a theory could for instance offer a better understanding for fundamental phenomena that are described under the names of 'creativity' and 'invention'.

Hence C-K theory was born at the crossroads of the crisis of industrial innovation and the scientific challenge of new 'models of thought' that account for generativity.

WHICH DISCIPLINES ARE INVOLVED IN C-K THEORY?

When Armand Hatchuel and Benoit Weil first formulated the C-K theory (Hatchuel andWeil, 2003, 2009), they wanted to articulate two separate research fields: works on ontology and the theory of knowledge and works on creativity. They remark that fuzzy notions such as the designer's 'brief', the 'technological challenge', the architect's 'vision' actually form propositions of a same kind that is called a 'concept' (C) in the C-K theory.

A concept is a perfectly rational and rigorous proposition but, contrary to propositions in 'knowledge' (K), it has no logical status: it is impossible to say whether the proposition is true or false, it is undecidable with available knowledge. A concept can be 'there are chairs without legs'. A concept C is hence clearly different from the propositions in K which all have a logical status (true or false).

C-K theory relies on the idea of distinguishing two spaces, C and K. And the great discovery is that these two spaces have very different structures and interact through clear operators. Their interaction provokes a dual expansion, leading to the generation of new objects and new knowledge.

This distinction reveals the logics of 'innovative design' that link the logics of creative ideation, chimera and desirable unknowns (C-space) and the logics of knowledge, modelling, inference, laws, rules and belief (K-space). Innovative design is neither limited to creativity nor reduced to an increase in knowledge about existing things. C-K theory models a process of dual expansion on the unknown and the known, stimulating each other. Knowledge stimulates creation and creation stimulates knowledge.

Hence C-K theory belongs first to the stream of works on 'models of thought' -just like 'decision theory' in its time. But it provokes a paradigm shift: from decision to design. The question is no more to 'take the right decision' (to optimize) between existing alternatives, in a given model. It consists in generating new and better alternatives. A manager is no more constrained to be a 'decision maker' -he can be a design maker (being a designer himself or organizing and supporting rigorous efficient design processes). This 'model of thought' is strongly generic to many disciplines: it helps management science to enter a 'postdecisional' paradigm [START_REF] Hatchuel | Strategy as Innovative Design: An Emerging Perspective[END_REF][START_REF] Masson | Strategic Management of Innovation and Design[END_REF]; it also supports much research in engineering sciences to shift from modelling and optimizing to designing [START_REF] Potier | How Innovative Design can contribute to Chemical and Process Engineering development? Opening new innovation paths by applying the C-K method[END_REF][START_REF] Le Masson | Design Theory -Methods and Organization for Innovation[END_REF]. Beyond engineering design and management science, it has several implications and uses today in many disciplines such as cognitive science, philosophy, logics, history, economics, sociology, agronomics, chemical engineering, mechanics and more.

CAN C-K THEORY EXPLAIN HOW NEW IDEAS POP UP, E.G., EUREKA MOMENTS?

C-K theory is today widely used in the analysis and experiments on ideation. Let's mention two recent results. 1. In the world of creativity and ideation, one issue is the so-called 'fixation'. There is 'fixation' when people in an ideation challenge, tend to propose similar ideas and are unable to explore more 'original' ideas. This paper was a first step for using design theory to address issues in creativity and ideation. This is now a very powerful stream of research. 2. Another stream of work was done to understand how the structure of knowledge influences creativity.

Recent research on C-K theory and mathematical models have shown that knowledge space should follow the so-called 'splitting condition' to support expansion.

We have tested the hypothesis in several situations. For instance, we studied how students are taught in 'industrial design' schools, which are supposed to be a place where creative people acquire knowledge to be more creative. And we have shown that in Bauhaus, one of the most famous industrial design schools, courses consisted in teaching splitting knowledge (Le Masson et al., 2016). We have studied how architects use drawing to split their own knowledge base [START_REF] Brun | Designing with sketches: The generative effects of knowledge preordering[END_REF].

ARE THERE PRACTICAL APPLICATIONS OF C-K THEORY FOR GEOSCIENCE AND ENGINEERING IN OIL AND GAS EXPLORATION AND PRODUCTION?

There are today many practical applications of C-K theory [START_REF] Hatchuel | Mulitple forms of applications and impacts of a design theory -ten years of industrial applications of C-K theory[END_REF]. Many companies are supporting the Chair of Design Theory and Methods for Innovation: big companies like Airbus, Dassault Systèmes, Renault, RATP, SNCF, ST Microelectronics, Thales; but also smaller one like Urgo, Ereie, Helvetia and Nutriset. We work with them to develop methods, processes and organizations that are adapted to the 'innovation departments' created in many companies.

Innovation directors are in need of methods, and they want to go beyond project management or brainstorming. With C-K theory, they can enrich and evaluate innovation projects more rigorously, they can evaluate the variety and originality of the proposed alternatives, they can evaluate the level of disruption and value creation (see [START_REF] Elmquist | The value of a 'failed' R&D project: an emerging evaluation framework for building innovative capabilities[END_REF].

In the oil and gas industry we have had many fruitful partnerships, in particular with Schlumberger, Vallourec and Technip. The recent experience with Technip is really impressive: this is the first time that social networks inside a company were used to support an innovative design process. Several hundreds of designers all over the world were able to collaborate in an innovative design process. This was a world first!

C-K THEORY EMPHASIZES COLLABORATIVE DESIGN. WHAT DOES THAT MEAN?

One of the issues in organizing innovative design consists in helping to work together in a creative way: how can one mobilize experts coming from different disciplines to propose creative concepts. It is well known that in such situations, fixations are reinforced and people tend actually to propose a consensual solution that is only poorly innovative. And brainstorming is not a solution -on the contrary -it has long been shown that brainstorming decreases the creativity of people put in a group instead of working separately! So how to overcome collective fixation? C-K theory helped to understand the multiple causes of collective fixation and led to propose original processes to overcome them. This is the so-called 'KCP process'. KCP is a way to 'linearize' a C-K design process, preserving generativity as much as possible. To make things simple, it reverses the logic of brainstorming: first share and accumulate knowledge and make a 'state of the non-art' (instead of 'forgetting what you know' or 'make a state of the art'); then force exploration to overcome fixations (instead of letting people explore without directions); and finally build a design strategy that manages the portfolio of projects (instead of selecting a couple of attractive ideas and rejecting many others). The results are very impressive (Hatchuel et al., 2009).

WHAT WOULD YOU LIKE STUDENTS TO TAKE AWAY FROM YOUR PRESENTATION AT EAGE PARIS?

I am sure that many of them are working on great innovative projects, or will have to in the future. And I hope that they will find in design theory a wellspring of methods and 'models of thought' that could help them to be more 'defixed' in their engineering work. Science and engineering is today a fantastic field for innovative design -and design theory and design methods aim at supporting the efficient development of new concepts that support sustainable growth and progress for our societies. Moreover the students will tomorrow be managers of scientists, engineers and designers. And I hope that they will keep in mind that managing innovative design is today a critical challenge. It requires new talents beyond 'intuition' and 'decision making'. I hope to give them the pleasure and the taste for innovative design!

"EX PLA M, SI RE CON E VOL ORP ORE PER RUM QUI AE PID ITIU M CON UT AB ISSE QUI A QUI SEQ UIS ELES AN ORI A SUM "

  When you work in innovative design you become a 'polymath' (as one of my colleagues Georges Amar said): you are interested in all fields of knowledge! There is no mystery: this is just because I am not alone! We are actually a full team of researchers working in innovative design -and what you see and what I have described is a very, very collective work. We try to apply our own theories and develop 'collaborative design' in research!

	ARE THERE OTHER AREAS OF RESEARCH THAT
	YOU ARE INTERESTED IN?
	YOU SEEM TO HAVE MANY ACADEMIC
	AND OTHER PROFESSIONAL COMMITMENTS.
	DO YOU HAVE ANY INNOVATIVE IDEAS
	FOR MANAGING YOUR TIME?
	www.eage.org/rs • page 9

SPECIAL recruitment

www.eage.org/rs • page 10


Abdelmalek Aboussoror
email: aboussororabdel@hotmail.com

Samir Adly
email: samir.adly@unilim.fr

A Fenchel-Lagrange Duality Approach for a Bilevel Programming Problem

Keywords: Two-level optimization, Convex analysis, Conjugate duality, Composed programming problems

Introduction

We are concerned with the following bilevel nonlinear optimization problem

(S) Min x∈X F (x, v(x)),
where v(x) is the optimal value of the lower level problem P(x) Min y∈Y f (x, y).

F : R p × R → R, f : R p × R q → R; X and Y are two compact convex subsets of R p and R q , respectively. The problem (S) is called a bilevel problem with the extremalvalue function v(•). It corresponds to a two-player game in which a leader announces first a strategy x ∈ X, to minimize his objective function F , and a follower reacts optimally by selecting a strategy y(x) ∈ Y , to minimize his objective function f . We assume that the reaction of the follower to the strategies of the leader has no impact on the constraints of the leader. Then, when the leader evaluates the performance of the follower by the optimal value v(x), he includes it in the objective function F , which leads to the formulation considered above. For many applications of such a problem, we refer, for example, to the interesting book [START_REF] Shimizu | Nondifferentiable and Two-level Mathematical Programming[END_REF]. However, when the performance of the follower is evaluated by his solutions, we obtain different formulations of the leader's problem, as the optimistic and the pessimistic formulations. For these interesting formulations, we refer, for example, to [START_REF] Shimizu | Nondifferentiable and Two-level Mathematical Programming[END_REF][START_REF] Anandalingam | A solution method for the linear static Stackelberg problem using penalty functions[END_REF][START_REF] Bard | Practical Bilevel Optimization: Algorithms and Applications[END_REF][START_REF] Dempe | A simple algorithm for the linear bilevel programming problem[END_REF][START_REF] Dempe | New necessary optimality conditions in optimistic bilevel programming[END_REF][START_REF] Dinh | Subdifferentials of value functions and optimality conditions for DC and bilevel infinite and semi-infinite programs[END_REF][START_REF] Aboussoror | Existence and approximation results involving regularized constrained Stackelberg problems[END_REF][START_REF] Aboussoror | Weak linear bilevel programming problems: existence of solutions via a penalty method[END_REF][START_REF] Lucchetti | Existence theorems of equilibrium points in Stackelberg games with constraints[END_REF], respectively. Note that (S) can be viewed as a composed programming problem. This remark will be the key of our investigation. As it is well-known, the problem (S) presents difficulties in the theoretical and numerical aspects, since its formulation includes a marginal function which, in general, is not differentiable. For different approaches concerning such a class of bilevel programming problems, we refer, for example, to [START_REF] Shimizu | Nondifferentiable and Two-level Mathematical Programming[END_REF][START_REF] Aboussoror | Bilevel programs with extremal value function: global optimality conditions[END_REF][START_REF] Ishizuka | Optimality conditions for quasi-differentiable programs with application to two-level optimization[END_REF][START_REF] Shimizu | Optimality conditions and algorithms for parameter design problems with two-level structure[END_REF][START_REF] Tanino | An algorithm for solving two-level convex optimization problems[END_REF].

In [START_REF] Aboussoror | Bilevel programs with extremal value function: global optimality conditions[END_REF], for the problem (S), global optimality conditions using min-max problems are given. These optimality conditions are based on a notion of stability of optimization problems and regularity of solutions. Other optimality conditions for some classes of bilevel programming problems with the extremal-value function using different directional derivatives and the subdifferential of the marginal function v(•) are given in [START_REF] Shimizu | Nondifferentiable and Two-level Mathematical Programming[END_REF][START_REF] Ishizuka | Optimality conditions for quasi-differentiable programs with application to two-level optimization[END_REF][START_REF] Shimizu | Optimality conditions and algorithms for parameter design problems with two-level structure[END_REF][START_REF] Tanino | An algorithm for solving two-level convex optimization problems[END_REF]. In this paper, adopting the Fenchel-Lagrange duality, which has been first introduced by Boţ and Wanka in [START_REF] Wanka | On the relations between different dual problems in convex mathematical programming[END_REF] for ordinary convex programming problems, we give the so-called Fenchel-Lagrange dual of the bilevel problem (S). Based on some results given in [START_REF] Wanka | Conjugate duality for multiobjective composed optimization problems[END_REF][START_REF] Boţ | Farkas-type results for inequality systems with composed convex functions via conjugate duality[END_REF][START_REF] Boţ | Duality for composed convex functions with applications in location theory[END_REF][START_REF] Wanka | On the relations between different duals assigned to composed optimization problems[END_REF], we first show that a strong duality holds between them. Then, we provide necessary and sufficient optimality conditions for (S) and its dual. These optimality conditions are given in terms of conjugate functions and subdifferentials, respectively. Finally, we show that the resolution of the dual problem is equivalent to the resolution of a one-level convex minimization problem whose objective function is expressed in terms of the conjugates of the functions involved. Assume that the obtained dual problem is easier to solve than (S). Therefore, this approach may give a possibility to solve indirectly the problem (S) via a one-level convex minimization problem.

The paper is organized as follows. In Sect. 2, we recall some fundamental definitions and results relating essentially to convex analysis that are needed later. In Sect. 3, under appropriate assumptions, we show that we have strong duality between (S) and its Fenchel-Lagrange dual problem. In Sect. 4, we provide optimality conditions for (S) and its dual. Finally, Sect. 5 is devoted to reducing the dual problem to a one-level convex minimization problem.

Preliminaries

In this section, we recall some fundamental definitions and results relating essentially to convex analysis that we will use in the sequel.

Let A be a nonempty subset of R n . We shall denote by ψ A and σ A the indicator and the support functions of the set A, respectively, defined on R n by

ψ A (x) := 0, if x ∈ A, +∞, if x ∈ A, and σ A (d) := sup x∈A d, x ,
where •, • , denotes the inner product of two vectors in R n , i.e., for x = (x 1 , . . . , x n ) T , and y = (y 1 , . . . , y n ) T , x, y = n i=1 x i y i . The relative interior of A, denoted by ri(A), is the interior of A relative to the smallest affine set containing A, equipped with the induced topology of R n . Definition 2.1 [START_REF] Boţ | Farkas-type results for inequality systems with composed convex functions via conjugate duality[END_REF] Let g : R n → R be a function, where R = R ∪ {±∞}, and let A be a nonempty subset of R n . The conjugate function of g relative to the set A is denoted by g * A and defined on R n by

g * A (p) := sup x∈A p, x -g(x) .
When A = R n , we get the usual Legendre-Fenchel conjugate function of g, usually denoted by g * . Definition 2.2 Let g : R n → R be a function. The function g is said to be R n +increasing iff for any x, y ∈ R n , x = (x 1 , . . . , x n ) T , y = (y 1 , . . . , y n ) T , with x i ≤ y i , ∀i ∈ {1, . . . , n}, we have g(x) ≤ g(y), where R n + denotes the non-negative orthant of R n , and the superscript T stands for transpose.

(f 1 • • • f m )(x) := inf x 1 ,...,xm∈R n x 1 +•••+xm=x m i=1 f i (x i ) .
For an extended real-valued function f : R n → R, we shall denote by dom f the effective domain of f , i.e., the set defined by

dom f := x ∈ R n /f (x) < +∞ .
We say that f is proper if f (x) > -∞ for all x ∈ R n and dom f = ∅.

Definition 2.4 Let f : R n → R ∪ {+∞} be a proper convex function. Let x ∈ dom f . The subdifferential of f at x, denoted by ∂f ( x), is the set defined by

∂f ( x) := x * ∈ R n /f (x) ≥ f ( x) + x * , x -x , ∀x ∈ R n ,
and any x * ∈ ∂f ( x) is called a subgradient of f at x.

Definition 2.5

Let A be a nonempty subset of R n , and x ∈ A. The normal cone to A at x denoted by N A ( x) is the set defined by

N A ( x) := x * ∈ R n / x * , x -x ≤ 0, ∀x ∈ A .
If A is convex, then ∂ψ A ( x) = N A ( x) (e.g., see [START_REF] Rockafellar | Convex Analysis[END_REF]).

Theorem 2.1 [START_REF] Rockafellar | Convex Analysis[END_REF] Let f 1 , . . . , f m : R n → R be proper convex functions. Assume that m i=1 ri(dom f i ) = ∅. Then, for any x ∈ R n , we have

m i=1 f i * (x) = f * 1 • • • f * m (x) = inf x 1 ,...,xm∈R n x 1 +•••+xm=x m i=1 f * i (x i ) ,
and the infimum is attained.

The Fenchel-Lagrange Duality Approach

In this section, we give a dual problem of (S) involving conjugate functions, called the Fenchel-Lagrange dual of (S). Then, under appropriate assumptions, we show that a strong duality holds between them. This interesting duality has been first introduced in [START_REF] Wanka | On the relations between different dual problems in convex mathematical programming[END_REF] for ordinary convex programming problems and afterwards used in several works (e.g., see [START_REF] Boţ | Farkas-type results for inequality systems with composed convex functions via conjugate duality[END_REF][START_REF] Wanka | On the relations between different duals assigned to composed optimization problems[END_REF][START_REF] Boţ | Conjugate duality in convex optimization[END_REF][START_REF] Boţ | Duality in Vector Optimization[END_REF]). Let h : R p → R p+1 be the function defined by

h(x) := (h 1 (x), . . . , h p (x), h p+1 (x)) T = (x, v(x)) T ,
i.e., for x = (x 1 , . . . , x p ) T ,

h i (x) := x i , for i = 1, . . . , p, h i (x) := v(x), for i = p + 1,
with v(x) the optimal value of the lower level problem P(x). Then, the problem (S) can be written as

(S) Min x∈X F (h(x)),
which is a composed programming problem. Note that the interesting and wide class of composed programming problems was extensively studied in the last decade. For papers dealing with such problems, we refer, for example, to [START_REF] Boţ | Farkas-type results for inequality systems with composed convex functions via conjugate duality[END_REF][START_REF] Wanka | On the relations between different duals assigned to composed optimization problems[END_REF] and references therein. For our approach, the problem (S) will be seen as a composed programming problem.

In the sequel, in order to give the dual of the bilevel programming problem (S), we adopt the procedure given by Boţ et al. in [START_REF] Boţ | Farkas-type results for inequality systems with composed convex functions via conjugate duality[END_REF] for composed programming problems. Then, we start our duality approach by considering the following minimization problem

(S ) Min x∈X,y∈R p+1 h(x)≤y F (y).

We will make the following assumptions.

Assumption 3.1 The function F is R p+1 + -increasing. Assumption 3.2 The function F is convex on R p+1 . Assumption 3.3 The function f is convex on R p × R q .
Remark 3.1 Under the above assumptions, the remarks are quite obvious, especially in the particular case. Proof 1. First, note that F is continuous on R p+1 as a finite convex function. Then, the result follows from the continuity of the composed function F • h, and the compactness of the set X. It follows that inf(S) is a finite real number.

2. Let x ∈ X. Then, (x, h(x)) is a feasible point to (S ). Hence, inf(S ) ≤ F (h(x)), and

inf(S ) ≤ inf x∈X F (h(x)) = inf(S).
Conversely, let (x, y) be a feasible point of (S ). Then, x ∈ X, i.e., x is feasible for (S). Since h(x) ≤ y, it follows from Assumption 3.1 that F (h(x)) ≤ F (y). Hence inf(S) ≤ F (h(x)) ≤ F (y). Since (x, y) is an arbitrary feasible point of (S ), it follows that inf(S) ≤ inf(S ).

Let (D) be the Lagrangian dual problem to (S ), i.e.,

(D)

Max

α≥0 α∈R p+1 inf x∈X y∈R p+1 F (y) + α, h(x) -y ,
and consider the following maximization problem in which the objective function is expressed in terms of the conjugate functions of F , α T h and ψ X (D * ) Max

α∈R p+1 + β∈R p -F * (α) -α T h * (β) -ψ * X (-β) ,
where for α = (α 1 , . . . , α p+1 ) T ∈ R p+1 , α T h denotes the function defined on R p and valued in R, by

α T h(x) = α, h(x) = p+1 i=1 α i h i (x) = p i=1 α i x i + α p+1 v(x),
with x = (x 1 , . . . , x p ) T . Using the fact that ψ * X = σ X , the dual problem (D * ) can also be written as

(D * ) Max α∈R p+1 + β∈R p -F * (α) -α T h * (β) -σ X (-β) ,
which is the formulation that we adopt in the sequel. In the literature, (D * ) is called the Fenchel-Lagrange dual problem to (S) (see [START_REF] Wanka | On the relations between different dual problems in convex mathematical programming[END_REF][START_REF] Wanka | On the relations between different duals assigned to composed optimization problems[END_REF]). The following proposition establishes that problems (D) and (D * ) have the same supremum. The proof corresponding to an ordinary composed programming problem can be found, for example, in [START_REF] Boţ | Farkas-type results for inequality systems with composed convex functions via conjugate duality[END_REF][START_REF] Wanka | On the relations between different duals assigned to composed optimization problems[END_REF]. For the convenience of the reader, we give the proof corresponding to our case.

F (y) + α, h(x) -y = inf y∈R p+1 F (y) -α, y + inf x∈X α, h(x) = -sup y∈R p+1 α, y -F (y) -sup x∈X 0, x -α, h(x) = -F * (α) -α T h * X (0).
On the other hand, since X is a nonempty convex set, we have ri(X) = ∅ (see [START_REF] Rockafellar | Convex Analysis[END_REF]). So that ri(dom

α T h) ∩ ri(dom ψ X ) = R p ∩ ri(X) = ri(X) = ∅.
Therefore, by Theorem 2.1, we have

α T h * X (0) = α T h + ψ X * (0) = α T h * (ψ X ) * (0) = inf β∈R p α T h * (β) + (ψ X ) * (-β) = inf β∈R p α T h * (β) + σ X (-β) .
Then,

sup α∈R p+1 + inf x∈X y∈R p+1 F (y) + α, h(x) -y = sup α∈R p+1 + -F * (α) -inf β∈R p α T h * (β) + σ X (-β) = sup α∈R p+1 + β∈R p -F * (α) -α T h * (β) -σ X (-β) .
That is, sup(D) = sup(D * ). Proof The result is deduced by using Remark 3.2, and Propositions 3.1 and 3.2. Let g : R p × R p+1 → R p+1 be the function defined by g(x, y) := g 1 (x, y), . . . , g p (x, y), g p+1 (x, y) T = h(x)y, that is,

g i (x, y) = x i -y i , for i = 1, . . . , p, g i (x, y) = v(x) -y i , for i = p + 1,
with x = (x 1 , . . . , x p ) T and y = (y 1 , . . . , y p , y p+1 ) T . Assume that the marginal function v(•) is not affine, which is the case, in general. So, the function g p+1 is not affine. Let Consider the following constraint qualifications (CQ) ∃x = (x 1 , . . . , x p ) T ∈ ri(X), ∃y = (y 1 , . . . , y p , y p+1 ) T ∈ R p+1 , ∃z ∈ Y such that x i ≤ y i , i = 1, . . . , p and f (x, z) < y p+1 , (CQ) ∃x ∈ ri X, ∃y ∈ R p+1 such that g i (x, y) ≤ 0, for i ∈ L, g i (x, y) < 0, for i ∈ N .

Note that the constraint qualification (CQ) is well-known in the literature and is used to ensure strong Lagrange duality for an ordinary convex program with its Lagrange dual (see [START_REF] Rockafellar | Convex Analysis[END_REF][START_REF] Elster | Einführung in die Nichtlineare Optimierung[END_REF]). On the other hand, it is not difficult to show that the constraint qualifications (CQ) and (CQ) are equivalent.

Remark 3.4

1. Under the Assumptions 3.2 and 3.3 and the data of problem (S), the constraint qualification (CQ) is always satisfied. This follows principally from the fact that for any x ∈ X, v(x) is a finite real number (Remark 3.1). Indeed, since ri(X) is nonempty, let x = (x 1 , . . . , x p ) T ∈ ri(X), and let z be a point in the compact set Y such that v(x) = f (x, z). Then, any point y = (y 1 , . . . , y p , y p+1 ) T ∈ R p+1 , verifying

x i ≤ y i , i = 1, . . . , p and f (x, z) < y p+1 , is suitable. That is, the constraint qualification (CQ) is fulfilled. 2. Let the Assumptions 3.1-3.3 hold. From Proposition 3.1, we have inf(S) = inf(S ). Since inf(S) ∈ R, it follows that inf(S ) > -∞.

The following theorem establishes that a strong duality between (S) and (D * ) holds. Proof (i) As quoted in the above remark, the constraint (CQ) is satisfied. Hence, since (CQ) is equivalent to (CQ) and inf(S ) > -∞ [see 2. of Remark 3.4], it follows that a strong duality holds between (S ) and (D) (e.g., see [START_REF] Rockafellar | Convex Analysis[END_REF][START_REF] Elster | Einführung in die Nichtlineare Optimierung[END_REF]). Therefore,

inf(S) = inf(S ) = sup(D) = sup(D * ),
where the first and the last inequalities follow from Proposition 3.1 and Proposition 3.2, respectively.

(ii) See, for example, [START_REF] Boţ | Farkas-type results for inequality systems with composed convex functions via conjugate duality[END_REF][START_REF] Wanka | On the relations between different duals assigned to composed optimization problems[END_REF].

Optimality Conditions for (S) and (D * )

In this section, under the Assumptions 3.1-3.3 and exploiting our duality, we provide optimality conditions for (S) and its dual (D * ). These optimality conditions are expressed in terms of conjugate functions and subdifferentials, respectively. Since the problems (S) and (D * ) are convex, we are only concerned with global solutions. On the other hand, recall that the problem (S) admits solutions (Proposition 3.1), and that (S) and (D * ) are in strong duality (Theorem 3.1).

The following theorems give respectively necessary and sufficient optimality conditions for (S) and its dual. The proofs can be found in [START_REF] Wanka | Conjugate duality for multiobjective composed optimization problems[END_REF]. Similar proofs are given in [START_REF] Boţ | Duality for composed convex functions with applications in location theory[END_REF] for the case of the Fenchel-Rockafellar duality. The following corollaries give the main results of this section. They provide necessary and sufficient optimality conditions for (S) and (D * ). In terms of the subdifferentials, we have the following result.

F (h( x)) + F * ( ᾱ) = ᾱ, h( x) , ( 1
)
ᾱ, h( x) + ᾱT h * ( β) = β, x , ( 2
)
σ X (-β) + β, x = 0. (3)
ᾱ ∈ ∂F (h( x)), (1 )
β ∈ ∂( ᾱT h)( x), (2 )
-β ∈ ∂ψ X ( x) = N X ( x). (3 )
Proof The conditions (1) and ( 2) are obviously equivalent to (1 ) and ( 2), respectively. Furthermore, remarking that ψ X ( x) = 0 (since x ∈ X), and using the fact that σ X = ψ * X , the condition (3) can be written as

ψ X ( x) + ψ * X (-β) = -β, x ,
which is equivalent to

-β ∈ ∂ψ X ( x) = N X ( x).

Reduction of (D * ) to a One-level Convex Minimization Problem

In this section, exploiting the particular form of the dual problem (D * ), and via the conjugacy operation, we will show that the resolution of the dual problem is equivalent to the resolution of two single-level (one-level) convex minimization problems. First, let us give the conjugate of the marginal function v(•) which will be needed in the sequel.

Proposition 5.1 Let the Assumption 3.3 hold. Let x * ∈ R p . Then, v * (x * ) = f * R p ×Y (x * , 0).
Proof First, recall that for any x ∈ R p , v(x) is a finite real number (Remark 3.1). Let x * ∈ R p . We have

v * (x * ) = sup x∈R p x * , x -v(x) = sup x∈R p x * , x -inf y∈Y f (x, y) = sup (x,y)∈R p ×Y x * 0 , x y -f (x, y) = f * R p ×Y (x * , 0).
As remarked, the dual problem (D * ) has an objective function which contains the conjugate function (α T h) * . However, the function α T h depends on the marginal function v(•) which is an output of the lower level problem. So, in the following, we try to avoid such a dependence. This allows us to formulate the dual problem (D * ) only in terms of the data of the problem (S). Then, we have the following result. Proposition 5.2 Let the Assumptions 3.1-3.3 hold. Then, the resolution of the dual (D * ) is equivalent to the resolution of the following one-level maximization problems

(D * 1 ) Max α 1 ≥0,...,αp ≥0 β=(α 1 ,...,αp ) T -F * (α 1 , . . . , α p , 0) -σ X (-β)
and

(D * 2 ) Max α=(α 1 ,...,αp ,α p+1 ) T α 1 ≥0,...,αp ≥0 α p+1 >0 β∈R p -F * (α) -α p+1 f * R p ×Y β -(α 1 , . . . , α p ) α p+1 , 0 -σ X (-β)
in the sense that

• sup(D * ) = max{sup(D * 1 ), sup(D * 2 )},
-F * (α) - p i=1 α i h i + α p+1 v(•) * (β) -σ X (-β) .
Let us calculate the value of A (α 1 ,...,α p ) (β). We have

A (α 1 ,...,α p ) (β) = sup t∈R p β, t -(α 1 h 1 + • • • + α p h p )(t) = sup t∈R p β, t -(α 1 t 1 + • • • + α p t p ) = sup t∈R p β -(
-F * (α) - p i=1 α i h i + α p+1 v(•) * (β) -σ X (-β) .
On the other hand, for α p+1 > 0, we have For illustration, we give the following simple example.

p i=1 α i h i + α p+1 v(•) * (β) = sup t∈R p β, t -α 1 t 1 -• • • -α p t p -α p+1 v(t) = α p+1 sup t∈R p β -(α 1 , . . . , α p ) T α p+1 , t -v(t) = α p+1 v * β -(α 1 , . . . , α p ) T α p+1 = α p+1 f * R p ×Y β -(
Example 5.1 Let X = Y = [0, 1], f and F be the functions defined on R 2 by

f (x, y) = 1 2 x 2 + y + 1 4 y 4 and F (x, t) = 1 2 x 2 + 1 2 t 2 , if x ≥ 0, t ≥ 0, 0, otherwise.
Then, the Assumptions 3.1-3.3 are satisfied. For x ∈ X, we have

inf P(x) = v(x) = 1 2 x 2 .
The bilevel programming problem that we consider is

(S) Min x∈X F x, v(x) = 1 2 x 2 + 1 8 x 4
whose unique solution is obviously x = 0 and inf(S) = 0. Let us verify this by using our duality approach. Note that, in this example, we have strong duality between (S) and its Fenchel-Lagrange dual problem (D * ) (Theorem 3.1). Let us calculate f * R×Y and F * . By simple calculation, we find Let us calculate the solution of (S) by using the conditions in Corollary 4.1. We have h(x) = (x, 1 2 x 2 ) T . Then, x ∈ X is a solution of (S) if and only if

f * (x * , y * ) = ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ 1 2 x * 2 + y * -5 4 , if y * > 2, x * ∈ R, 1 2 x * 2 + 5 4 (y * -1) 4 3 , if 1 ≤ y * ≤ 2, x * ∈ R, 1 2 x * 2 , if y * < 1, x * ∈ R, and
F * (x * , t * ) = +∞, if (x * , t * ) = (0, 0), 0, if (x * , t * ) = (0, 0).
F (h( x)) + F * ( ᾱ) = ᾱ, h( x) , (4)
ᾱ, h( x) + ( ᾱT h) * ( β) = β, x , (5)

σ [0,1] (-β) + β, x = 0, (6)
with ᾱ = ( ᾱ1 , ᾱ2 ) T . So that, from the first equation, we have

x2 1 + 1 4 x2 = 0,
whose unique solution is x = 0. Besides, x satisfies with ᾱ and β (5) and ( 6). Hence, x is the unique solution of (S).

Remark 5.2

1. The same duality approach can be applied via appropriate modifications to the case where the constraints of the leader depend on the optimal value of the follower, i.e., the case

(S) Min x∈X G(x,v(x))≤0 F (x, v(x)),
where G : R p × R → R. 2. Viewing (S) as a composed programming problem, other duality approaches can be applied to (S), as Lagrange duality and Fenchel duality. Relations between these dualities and the Fenchel-Lagrange duality are given in [START_REF] Wanka | On the relations between different duals assigned to composed optimization problems[END_REF].

Conclusions

The bilevel programming problem (S) which, in general, is not differentiable is difficult to solve in view of the existence of the marginal function v(•) in its formulation. For such a problem, we have considered a duality approach by introducing its Fenchel-Lagrange dual problem (D * ). This type of dual problem has been first introduced by Boţ and Wanka in [START_REF] Wanka | On the relations between different dual problems in convex mathematical programming[END_REF] for ordinary convex programming problems. Under appropriate assumptions, and based on some results given in the literature for composed programming problems, we have shown that a strong duality holds between (S) and (D * ). Then, for problem (S) and its dual we have provided optimality conditions which are expressed in terms of conjugate functions and subdifferentials, respectively. Finally, in Proposition 5.2, we have reduced the dual problem to a one-level convex minimization problem. Therefore, this duality approach gives the possibility to solve the bilevel programming problem (S) via a one-level convex minimization programming problem.

Definition 2 . 3

 23 Let f 1 , . . . , f m : R n → R be functions. The infimal convolution of f 1 , . . . , f m is the function denoted by f 1 • • • f m , and defined on R n by

1 .Proposition 3 . 1

 131 The Assumption 3.1 is extensively used in the study of composed programming problems. It allows us to establish a relation between the problems (S) and (S ), and to preserve the convexity of functions under composition. 2. From the convexity of the set Y and the function f , we deduce that the marginal function v(•) is convex on R p . It follows that the vector function h is also convex on R p . If, moreover, the Assumptions 3.1 and 3.2 are satisfied, then the problem (S) is convex. 3. Under the Assumption 3.3, we deduce that, for any x ∈ R p , v(x) is a finite real number. This follows from the continuity of the function f (x, •) and the compactness of Y . Furthermore, v(•) is continuous on R p as a finite convex function. Let inf(S) and inf(S ) denote the infimal values of the problems (S) and (S ), respectively. Then, we have the following result. Let the Assumptions 3.1-3.3 hold. Then, 1. The problem (S) has at least one solution, 2. inf(S) = inf(S ).

Remark 3 . 2

 32 By weak duality, we have inf(S ) ≥ sup(D), where sup(D) denotes the supremum of the dual problem (D).

Proposition 3 . 2

 32 Let the Assumptions 3.2 and 3.3 hold. Then, sup(D) = sup(D * ).

Corollary 3 . 1

 31 Let the Assumptions 3.1-3.3 hold. Then, the weak duality holds between (S) and (D * ).

LRemark 3 . 3

 33 := {i ∈ {1, . . . , p + 1}/g i is an affine function}, N := {1, . . . , p + 1} \ L. It follows that L = {1, . . . , p} and N = {p + 1}. If v(•) is affine, then L = 1, . . . , p + 1 and N = ∅.

Theorem 3 . 1

 31 Let the Assumptions 3.1-3.3 hold. Then, a strong duality holds between (S) and (D * ), i.e., (i) inf(S) = sup(D * ); (ii) The dual (D * ) admits solutions.

Theorem 4 . 1 (

 41 Necessary optimality conditions) Let the Assumptions 3.1-3.3 hold. Let x ∈ X and ( ᾱ, β) ∈ R p+1 + × R p be solutions to (S) and (D * ), respectively. Then, x and ( ᾱ, β) satisfy the following necessary optimality conditions

Theorem 4 . 2 (

 42 Sufficient optimality conditions) Let the Assumptions 3.1-3.3 hold. Let x and ( ᾱ, β) be feasible points to (S) and (D * ), respectively. Assume that they satisfy the conditions (1)-(3) in Theorem 4.1. Then, x solves (S) and ( ᾱ, β) solves (D * ).

Corollary 4 . 1

 41 Let the Assumptions 3.1-3.3 hold. Let x and ( ᾱ, β) be feasible points to (S) and (D * ), respectively. Then, x and ( ᾱ, β) solve (S) and (D * ), respectively, if and only if the conditions (1)-(3) are satisfied. Proof The result follows by using Theorems 4.1 and 4.2.

Corollary 4 . 2

 42 Let the Assumptions 3.1-3.3 hold. Let x and ( ᾱ, β) be feasible points to (S) and (D * ), respectively. Then, x and ( ᾱ, β) solve (S) and (D * ), respectively, if and only if the following conditions are satisfied

  On the other hand, for problems (D * i ), i = 1, 2, we have sup(D * 2 ) = -∞ and sup(D * 1 ) = 0, where sup(D * 1 ) is attained at ( ( ᾱ1 , ᾱ2 ) T β ). So that sup(D * ) = sup(D * 1 ) = 0, attained at ( ( ᾱ1 , ᾱ2 ) T β ) = ( (0,0) T 0 ). By strong duality, we have sup(D * ) = inf(S) = 0.

  α 1 , . . . , α p ) T , t

	with t = (t 1 , . . . , t p ) T . So that
	sup(D * ) = sup	sup	-F * (α 1 , . . . , α p , 0) -σ X (-β) ,
		α 1 ≥0,...,αp ≥0
		β=(α 1 ,...,αp ) T
	sup
	α=(α 1 ,...,α p+1 ) T
	α 1 ≥0,...,αp ≥0 α p+1 >0 β∈R p
		=	+∞, if β = (α 1 , . . . , α p ), 0, if β = (α 1 , . . . , α p ),

  Remark that the objective functions of problems (D * 1 ) and (D *2 ) are expressed in terms of the conjugate functions of F , f and ψ X (since σ X = ψ * X ). 2. As it is well-known, the functions F * , f * and σ X are convex. Besides, the constraint sets of problems (D * 1 ) and (D * 2 ) are also convex. It follows that (D * Consequently, the resolution of the problem (D * ) is equivalent to the resolution of the two single-level concave maximization problems (D * 1 ) and (D * 2 ). Therefore, the problem (D * ) is reduced to a single-level convex minimization problem.

	α 1 , . . . , α p ) T α p+1 where the last equality follows from Proposition 5.1. Now, consider the following , 0 , maximization problems (D * 1 ) Max α 1 ≥0,...,αp ≥0 β=(α 1 ,...,αp ) T -F * (α 1 , . . . , α p , 0) -σ X (-β) and (D * 2 ) Max α=(α 1 ,...,αp ,α p+1 ) T α 1 ≥0,...,αp ≥0 α p+1 >0 β∈R p -F * (α)-α p+1 f * R p ×Y β -(α 1 , . . . , α p ) α p+1 , 0 -σ X (-β) . Then, we have 1. 1 ) and (D * 2 ) are concave maximization problems (equivalent to convex minimiza-sup(D Remark 5.1 tion problems).

* ) = max sup(D * 1 ), sup(D * 2 )}.

It follows that (α, β) is a solution of (D * ) if and only if (α, β) is a solution of (D * i ) with sup(D * i ) ≥ sup(D * j ), i = j , i, j ∈ {1, 2}.


Junaid Ahmed Khan
email: junaid.khan@inria.fr

Cedric Westphal
email: cedric@soe.ucsc.edu

Yacine Ghamri-Doudane

A Popularity-aware Centrality Metric for Content Placement in Information Centric Networks

Keywords: Information/Content Centric Networking, Content Caching, Fog Networking, Content Offload

Information-centric networks enables a multitude of nodes, in particular near the end-users, to provide storage and communication. At the edge, nodes can connect with each other directly to get content locally whenever possible. As the topology of the network directly influences the nodes' connectivity, there has been some work to compute the graph centrality of each node within the topology of the edge network. The centrality is then used to distinguish nodes at the edge of the network. We argue that, for a network with caches, graph centrality is not an appropriate metric. Indeed, a node with low connectivity (and thereby low centrality) that caches a lot of content may provide a very valuable role in the network.

To capture this, we introduce a popularity-weighted contentbased centrality (P-CBC) metric which takes into account how well a node is connected to the content the network is delivering, rather than to the other nodes in the network. To illustrate the validity of considering content-based centrality, we use this new metric for a collaborative caching algorithm. We compare the performance of the proposed collaborative caching with typical centrality based, non-centrality based, and non-collaborative caching mechanisms. Our simulation implements P-CBC on three random instances of large scale realistic network topology comprising 2, 896 nodes with three content replication levels. Results shows that P-CBC outperforms benchmark caching schemes and yields a roughly 3x improvement for the average cache hit rate.

I. INTRODUCTION

Under the pressure of increasing bandwidth demand, service providers have been trying to offload traffic away from their networks unto local caches, either co-located with access points from WiFi networks or small cells or base stations, or provided by other users in an ad hoc fashion.

Peers, small cell base stations, and access points in a local area near a user may offer storage or caching capability for the users of the network. They may also have a wide range of connectivity varying from very poor in sparse areas to very rich in dense environments. To better offload content away from the wide area networks, these nodes can cache content. Which content should depend on how connected the node is, and how popular the content.

Centrality [START_REF] Borgatti | Centrality and network flow[END_REF], a concept from graph theory typically applied to social networks, is used to find important nodes in a graph. A high centrality score reflects a high topological connectivity for a node in the network. Typical centrality measures are: degree (the number of directly connected nodes), closeness (the average length of the shortest paths between the node and all other nodes in the graph), betweenness (the number of shortest paths between all pairs of nodes in the graph going through a specific node), and eigenvector centrality (a measure of node influence in the network).

Computing centrality on the topological graph yields interesting insights. Yet it fails to capture that, in network of caches, the consumer is interested in connecting to the content, not to a specific node. If a node is well connected, but holds content of little value, it is not useful to the user. It has low centrality, in the context of content delivery, despite having a high centrality within the topological graph.

To address this, we utilize the concept of Popularity-Weighted Content-Based Centrality (P-CBC). We introduce here a weighted content-based centrality metric. Namely, for a cache v, its P-CBC is calculated as a function of the number of shortest paths which go through v for content x, the popularity of x and the number of shortest paths from the users to x. It is defined more formally in Section III.

To show the usefulness of the P-CBC, we propose to place content in caches depending on the cache's P-CBC metric. Namely, we suggest to place content in a way that ensures the P-CBC metric is high for most caches, so that all users have connectivity to the most popular content, and not only those in densely covered areas.

We evaluate our proposed P-CBC-based content placement policy by simulations with three different realistic typologies and three content replication ratios. The results show that the proposed P-CBC-based content placement outperforms typical centrality schemes, or schemes without coordination. Our contributions can be summarized as follows:

• We introduce the concept of Popularity-Weighted Content-Based Centrality (P-CBC), which we believe is better suited for network of caches (such as Information-Centric Networks) than traditional graph centrality; • We introduce a scalable method to compute P-CBC without a priori knowledge of the content placement, based only upon replication rules and some basic assumptions about content placement;

• We present a P-CBC-based content placement algorithm which takes into account the number of paths to content passing through a node to decide where to cache in the network; • We evaluate our algorithm through simulations which show a significant improvement. The remainder of the paper is organized as follows. Section II discusses the related work. In Section III we define our network model and introduce our content-based centrality metrics. Section IV shows our content placement algorithm. In Section V, we discuss the performance evaluation and results. Section VI concludes the paper along with insights into future directions.

II. RELATED WORK

Content Caching has been studied for some time by the research community, spanning a wide spectrum, including Small Cell Networks (SCNs) [START_REF] Bas ¸tug | Cache-enabled small cell networks: Modeling and tradeoffs[END_REF], [START_REF] Bharath | A learning-based approach to caching in heterogenous small cell networks[END_REF], Content Distribution Networks (CDNs) [START_REF] Hamidouche | Many-to-many matching games for proactive social-caching in wireless small cell networks[END_REF] and Information/Content Centric Networking (ICNs/CCNs). For example in [START_REF] Sourlas | Distributed cache management in information-centric networks[END_REF], distributed cache management decisions are made in order to efficiently place replicas of information in dedicated storage devices attached to nodes in the network using ICN. Similarly [START_REF] Wang | Design and evaluation of the optimal cache allocation for content-centric networking[END_REF] addresses the distribution of the cache capacity across routers under a constrained total storage budget for the network. The authors found that network topology and content popularity are two important factors that affect where exactly should cache capacity be placed. [START_REF] Yu | Congestionaware edge caching for adaptive video streaming in information-centric networks[END_REF] looked at pushing content to the edge to anticipate network congestion, while [START_REF] Azimdoost | Fundamental limits on throughput capacity in information-centric networks[END_REF] computed the capacity of an ad-hoc network of caches. [START_REF] Ren | Magic: a distributed max-gain in-network caching strategy in information-centric networks[END_REF] looked at how content caches are connected in relation to the users and the servers, but did not offer a systematic approach of contentbased centrality.

In a recent work [START_REF] Li | Pricing and resource allocation via game theory for a small-cell video caching system[END_REF], game theory is exploited for caching popular videos at small cell base stations (SBSs). Another work, [START_REF] Mangili | Bandwidth and cache leasing in wireless information centric networks: a game theoretic study[END_REF] proposed a game theoretic approach in ICN to stimulate wireless access point owners to jointly lease their unused bandwidth and storage space to a content provider under partial coverage constraints. Both papers targeted a pricing model instead of providing an efficient content placement solution.

[12] defines a "conditional betweenness centrality" and uses this metric to chooses which nodes will cache the content. Socially-Aware Caching Strategy (SACS) [START_REF] Bernardini | Socially-aware caching strategy for content centric networking[END_REF] for Content Centric Networks (CCNs) uses social information in order to privilege influential users in the network by pro-actively caching the content they produce. The authors detect the influence of users within a social network by using the Eigenvector and PageRank centrality measures.

Another centrality based caching approach in CCN is presented in [START_REF] Rossi | On sizing ccn content stores by exploiting topological information[END_REF] where the sizing the content store is based upon centrality. The authors exploit different centralities (betweenness, closeness, stress, graph, eccentricity and degree) to heterogeneously allocate content store at nodes instead of homogeneous allocation. It is proposed that a simple degree centrality based allocation is sufficient to allocate content store. Similarly, [START_REF] Chai | Cache "less for more" in information-centric networks[END_REF] shows that a higher cache hit rate can be achieved if content is cached at high betweenness centrality nodes. Similar to this work, [START_REF] Khan | A content-based centrality metric for collaborative caching in information-centric fogs[END_REF] considers content-based centrality, but does not take into account the popularity of the content.

We argue that the topological connectivity only partially relates to the content, and there is a need to consider the content reachability in the network not addressed in the prior art. A well connected node in the topological graph is not necessarily closer to end-users requesting the content. To the best of our knowledge, we are the first to propose to compute a content-based centrality.

III. POPULARITY-WEIGHTED CONTENT-BASED CENTRALITY

A. System Model 1) Connectivity Model: We assume that nodes are connected to a proximity network (also denoted as fog network in some places) through local, ad hoc connections. The connectivity between nodes is modeled by a graph G(V, E v ), where V = {v} is the set of nodes and E v (t) = {e jk (t) | v j , v k ∈ V, j = k} is the set of edges e jk (t) modeling the existence of a communication link between nodes j and k at time t. We assume the time is slotted: T = (t 1 , t 2 , ...) as a sequence of regular time-slots, where the k th time-slot is represented as t k = [t k , t k+1 ). We assume that during a particular time-slot the content placement and the connectivity are stable. In practice, the nodes will stay connected for a period of minutes or hours, depending on the application.

2) Caching Model: We define the set of known content as X = {x 1 , . . . , x N } for a catalog of N pieces of content, where x j is an indivisible content chunk in the network. In the remaining of the paper, we will deal with individual content chunks x i ∈ X, however a larger size content can be composed of several such content chunks. The nodes can fetch the content either from the service provider using the operator's infrastructure link or locally from peers in the fog, using a low-cost connectivity.

Definition: (Empirical Content Popularity) The content popularity is represented by the probability p x = λ(l,t) Λ(l,t) as a measure of the user interests for content x at location l and time t. Here, λ(l, t) represents the number of interest for the content x at location l and time t and Λ = Xv λ(l, t) is the total interests for all contents items. The content popularity can be shared with the nodes using three approaches, (i) Offline method by the content operator as a control message. (ii) Local monitoring by the nodes taking into account the number of user interests for the content, and (iii) part of content header shared by a service provider.

B. A Popularity-Weighted Content-Based Centrality Metric

Figure 1 shows an illustration to explain the concept of content-based centrality. Here the node v 1 is on the path from the users to the content in the server, but only for the cache misses for v 2 , v 3 or v 4 , and for the users directly connected to v 1 . Therefore, for users connecting to content that is cached at v 4 or v 3 , v 1 is not on the path and therefore has very low centrality.

However, for cache misses at the other nodes v 2 , v 3 , v 4 , all requests will go through v 1 and therefore v 1 will have very high centrality as all the traffic will go towards the origin server.

It is easy to see that the usual topological definition of centrality should therefore be modified as it varies on the type of content and where this content is cached. If all the nodes v 1 , v 2 , v 3 and v 4 keep a copy of the most popular content, then v 1 will have low centrality for the most popular content. Therefore the rate of request going through v 1 will be low as well. Therefore, both the content and its popularity needs to be taken into account to compute the centrality of v 1 in an information-centric network.

Other typical node-based centrality measures such as degree, closeness, betweenness and eigenvector consider the node v 2 as the highest centrality node as well, independently of where the content is located and how it is being accessed.

Content that is popular will generate more traffic, therefore the nodes that offer paths for this content should also have a higher content-based centrality. Therefore we offer the following definition of popularity-weighted content-based centrality:

Definition: the Popularity-Weighted Content-Based Centrality (P-CBC) of a node v is the weighted sum of the ratio of the number of shortest paths from all users to all content that passes through the node v to the total number of shortest paths between all the (user,content) pairs, where the sum is weighted by the popularity of the content.

Formally, for a node v, and for a probability distribution p x for the content x ∈ X and if σ v (u, x) is the number of shortest paths from user u to content x going through node v and σ(u, x) the total number of shortest paths between u and x, then:

P-CBC(v) = u,x σ v (u, x) σ(u, x) × p x (1)
The popularity-weighted CBC can then normalized by the number of possible paths to all content in the network such as:

(P-CBC(v)) normal = P -CBC(v)-minw∈V (P -CBC(w)) maxw∈V (P -CBC(w))-minw∈V (P -CBC(w)) (2)
We have used a modified version of Betweenness centrality in our definition of P-CBC, but we could use other forms of centrality as well, such as Closeness or Eccentricity for instance. Closeness P-CBC would measure the inverse of the weighted sum of the path length from users to content for instance.

C. Practical and Scalable Computation of P-CBC

Computing the proposed centrality appears to be extremely difficult, since the catalog X may be very large, the topology complex, and it requires knowing the content placement a priori, whereas we would like to compute the content-based Figure 1: An example of Content-based Centrality centrality so as to guide the content placement. Namely we would like an idea of how well a node connects users to the content before we assign the content to it. Howevever, there is a practical method to compute P-CBC at each node.

Our solution is to note that the centrality of a piece of content does not depend on the specific chunk x j , but rather, on the relative placement of the multiple copies of a chunk x j . For instance, if N m objects are not cached anywhere in the network (and only at the origin server), their contribution to P-CBC(v) is equal to N m times the number of shortest paths to the origin server going through v divided by the number of shortest paths to the origin server, weighted by the aggregated popularity of all the N m objects. We do not need to know which N m objects are cache misses, only that there are N m of them and what is their expected popularity. And for these N m objects, only one computation is required using a traditional computation of centrality.

In the case of these N m objects, their popularity will be that of cache misses, namely the tail of the popularity distribution. For content that is cached in the network, we need a different method.

In practice, content will be replicated in the network following some simple placement rules and heurisitcs. Namely, the most popular content will be placed at the edges but the rest of the cached content will be placed only at a handful of nodes so as to ensure that more content is cached within the proximity network.

More formally, a simple content placement rule is that a fraction of the cache in each node v will be allocated to the most popular content and this content will be at all nodes. The rest of the cached content will be placed in at most one node in the proximity (or fog) network so as to cover more content. Other rules are possible, but we will demonstrate how to compute P-CBC under this one rule for illustration purpose.

We define by α the fraction of the cache allocated to that most popular content that is common to all node. α corresponds to our replication policy. For a total cache size of b v at node v (assumed here to be uniform for all nodes, but this assumption can be relaxed), C = αb v contains content that is common at all the caching nodes (i.e. most popular content), while D v = (1 -α)b v is the fraction of node caches with unique (different) content compared to other nodes. With the knowledge of α, we can compute the P-CBC without knowing which content is placed at which node. The only knowledge is the rule that C content is common and each node v contains D v content that is specific to it.

However, in the content placement phase, we need to ensure that this replication rule is satisfied, by attempting to place content such that a fraction α is replicated at all nodes, and the rest is unique to each node.

Since the most popular content is the one that will be at all nodes (in C) and that the next most popular content will be spread over the caches (in each D v for cache v), then we can compute the centrality as:

P-CBC(v) = u,C σ v (u, C) σ(u, C) × p C + u,Dv σ v (u, D v ) σ(u, D v ) × p Dv , p C = C i=1 p i , p Dv = 1 M M S i=C+1 p i ,
where we have M caches with D v content unique to the node v, p C and p Dv are sum of the probability for content in C and D v respectively. This way, the popularity-based centrality is computed per cache and not per content. This is the same complexity as traditional centrality. Yet it gives us a metric of the connectivity of the users to the content. This specific replication policy of splitting the cache into C and D v is a simple first step, to demonstrate the feasibility of a content-based centrality metric. We can define more sophisticated rules that allow to compute P-CBC without knowing the specific content placement. It nonetheless gives us a simple tuning parameter α to know which content makes sense to be duplicated everywhere to be accessible.

IV. CONTENT PLACEMENT ALGORITHM

The problem of content placement can be formulated as follows:

edymaximize

s v P-CBC(v) edysubject to x∈X b x v ≤ b v , ∀v ,
where s is content placement for the content cached in the local network. Thus, the objective function maximizes the content from a particular service provider available at the nodes in the fog near the users. The constraint considers that the node buffer where a content cached at an individual node buffer should not exceed the maximum available threshold space. We also consider a defined replication factor α where for a node cache size b v , C = αb v contains content common

Algorithm 1 Content Placement Algorithm 1: INPUT: V, X, b t v , ∀v ∈ V , p x , ∀x ∈ X, α 2: OUTPUT: s ⊆ V ,X s , X v ∈ X 3: Initialize s = φ, b v * = φ, X s = φ 4: for each location l ∈ L, time-slot t ∈ T do 5: v * = arg max v∈V (P-CBC(v)), v * / ∈ s 6: while (b v * ≤ C) do 7: b v * ← arg max x∈X (x, p x ), 8: Update b v * , X v * 9: X s = X s ∪ X v * 10:
end while 11:

while

(b v * ≤ b t v ) do 12: b v * ← arg max x∈X,x / ∈Xs (x, p x ), 13: Update b v * , X v * 14: X s = X s ∪ X v * 15:
end while 16:

s = s ∪ v * 17: end for 18: return s at all nodes, while D v = (1 -α)b v contains content unique to this node.

The P-CBC is initially computed without any content placement, using the replication rule from the previous section. Then, the distributed content placement is optimized at colocated nodes using Algorithm 1. For a location l and timeslot t, the node v * ∈ V with the highest P-CBC becomes the delegate to locally cache content in the fog as shown in Line 5. It initializes the fog formation by creating the subset s and caches the most popular content while respecting the replication factor α for its respective storage buffer (Line 6). It continues caching content with decreasing popularity till the storage conditions based on the replication factor α are met. Once the storage buffer is at C or αb v , it updates the cached content and start filling the remaining content with decreasing popularity. The condition in Line 11 continues adding content until the node buffer b v attains its maximum threshold to cache content as indicated in our optimization constraint. The cached content is updated in the fog s (Line 14) and the node adds itself to the fog (Line 16). Similarly, in a decreasing order of node P-CBC, the remaining nodes cache content in the fog x with same content at αb v and different at (1 -α)b v .

Algorithm 1 ensures that a maximum amount of popular content X s are cached in the fog which in turn maximizes our objective function. At the same time, it yields low overhead as it requires a node to exchange information regarding its cached content with its one hop neighbors where the frequency of such exchanges as well as the P-CBC computation depends on the application requirements. Therefore, the complexity is proportional to the amount of node neighbors or simply its one hop degree.

V. NUMERICAL EVALUATION

We evaluate the proposed P-CBC and our associated caching algorithm using NS-3 where the named-data networking model of the ICN architecture is implemented. Three different topologies are extracted from a realistic large scale trace of 2, 986 nodes (vehicles) in Köln, Germany in order to validate the scalability of our caching approach. This allows us to evaluate the concept of fogs on realistic topologies reflecting connectivity in an urban environment. The topologies are the time snap-shots of the network connectivity at the initial, at 30 th minutes and at 60 th minutes respectively.

A. Simulation Scenario

The simulation scenario implements consumer nodes which generate interests for a pre-known content sequence of 100 unique items following a Zipf distribution (coefficient=1), i.e. more frequent interests for more popular content. Any provider node already caching the content responds to the consumer interest where interests can be routed using any p2p routing schemes, though we use [START_REF] Khan | Strive: Socially-aware threetier routing in information-centric vehicular environment[END_REF] as the social aware interest forwarding scheme. We allow intermediate nodes with uniform buffer size to perform in-network caching. We consider 30% of the nodes as consumers, 30% as providers (up to 900 caching nodes) nodes and the remaining nodes with disabled caching in order to accurately evaluate the performance of caching nodes.

We also define α as a content replication factor where for a node buffer b v , αb v contains content which is same at all nodes in the fog, while (1 -α)b v is the buffer space for the cached content unique to each node. The Köln 6 × 6km 2 city center is divided into 36 neighborhoods, i.e. all nodes are divided in to 36 fogs of 25 nodes in each fog.

As a first step, we randomly populate the caches of nodes in the fog with content in order to compute each node P-CBC. Random interests are generated. Then, we implement the collaborative placement Algorithm 1 where the highest P-CBC node caches the most popular content. Similarly content are populated at the remaining nodes' cache with decreasing content popularity and node P-CBC score. We implement our proposed P-CBC as well as a variant with no popularity con-sideration in computing centrality denoted as CBC, however content are placed using the Algorithm 1. We compare both P-CBC and CBC with the following three different caching approaches:

• Centrality-based Caching popular content at fog of high Degree, Closeness, Betweenness and Eigenvector centrality nodes. Algorithm 1 is implemented using each scheme where the most popular content is placed at the highest centrality node, then remaining content are placed at the nodes with decreasing node centrality and content popularity. • Non-centrality based Social-unaware approach by caching greedily popular content at all nodes in the fog along a Least Recently Used (LRU) based content replacement policy. • Non-collaborative based approach where no fog is formed between nodes and each individual node cache indifferently. P-CBC is used to identify nodes. The following performance metrics are used to evaluate P-CBC and the proposed collaborative caching algorithm:

• Cache Hits: It is the average number of content responds from the node cache, calculated as the ratio of the number of content responses to the number of received interests by the nodes. • Success Rate: this is the ratio of the number of interests responded with content or forwarded by the nodes to the number of generated interests.

B. Simulation Results

1) Cache Hits:

We computed the cache hit rate for each scheme; (i) Fog with P-CBC, CBC without considering popularity, Degree, Closeness, Betweenness and Eigenvector centrality, (ii) non-centrality based fog, and (iii) no fog where individual nodes cache indifferently. Figure 2 shows the average cache hit rate of the nodes in fog classified by P-CBC. We compare the hit rate of our approach for three topologies from the Cologne trace and three replication ratios (α = 25%, 50% and 75%) to find the impact of varying underlying topologies. It is shown that the average cache hit rate achieved differs with respect to topology. Furthermore, we observe for all topologies that there is an increase in the cache hit rate with increasing content replication ratio. Thus, increasing popular content placement results in high hit rate with no impact of the underlying network topological connectivity.

Similarly, we implement benchmark centrality schemes by first placing popular content at the highest centrality node identified by each scheme. Then, following a decreasing node centrality order, we place the content at the set of nodes in the fog with decreasing content popularity order. Figure 3 shows the hit rate comparison where Figures 3a, 3b and3c show result for each topology. Thus, irrespective of the network topology, P-CBC achieves a high cache hit rate when compared to all other approaches. It resulted in around 55% hit rate for Topology 1, around 55 -73% for Topology 2 and around 57 -73% for the Topology 3. P-CBC is followed by simple CBC where it resulted in similar performance for 25% and 50% replication ratio where the similar performance is due to relatively less amount of popular content commonly cached at nodes. However, P-CBC outperforms it for a cache replication ration of 75% since the amount of popular content in the cache are increased. All the centrality schemes resulted in substantially higher hit rate than the case without non centrality (social-unaware). For all three topologies, this resulted in around 10% hit rate with a maximum of 18% cache hit rate for Topology 1. This validates the fact that P-CBC not only works better for the case when more popular content are common between caches but also outperforms other schemes in the case of less amount of popular contents commonly cached at nodes in a fog.

Figure 3 also depicts the result by implementing a case where there is no collaboration between the caching nodes, namely no fog scenario. It resulted in slightly better performance than the case of non-centrality based caching, though it achieves a lower average hit rate where it merely achieves around 20% cache hit rate. Thus, the overall comparative analysis of cache hit rate on three different topologies and three content replication ratios reveals that P-CBC achieves a better hit rate. It is because it consider jointly the number of paths to content and its popularity instead of considering nodes as a content-centric approach.

2) Success Rate: We evaluate the success rate as the content responded or forwarded by the nodes in the Fog. In Figure 4, we show the average success rate achieved by the nodes in the Fog classified using P-CBC. Similar to the hit rate, we analyze three topologies and three replication ratios. Each topology resulted in a different success where Topology 3 shows the best performance with more than 60% success rate for all replication ratios, followed by Topology 1 and Topology 2, thus suggesting that topology impacts performance. Another observation is that the success rate results from all topologies follow similar trend, thus validates the robustness of P-CBC when applied to different topologies. We see in the case of Topology 1 and 2 that by varying the replication ratio, a slight increase in the success rate is achieved from 75% to 50% replication ratio. This suggest that for a node, it is optimal to constantly keep more amount of popular content.

Figure 5 shows a comparative analysis of the success rate achieved by different caching approaches. We observe that overall, P-CBC outperforms all other approaches, yielding an average success rate of up to 68, 67 and 70% for Topology 1, 2 and 3 respectively. An interesting behavior is seen in the case of Topology 1 (Figure 5a) where fogs based on P-CBC, degree and betweenness centrality have similar success rate, though their score differs between replication ratio. For 25% replication ratio, both degree and betweenness centrality show a higher success rate (60%) than P-CBC, though for 75% replication ratio, P-CBC dominates both of them. We investigated this behavior and found that since both betweenness and degree are node-centric metrics, and therefore better connected nodes at the relative center of the topology and are acting as bridge between large number of nodes, thus resulting in a higher success rate. This underlies the fact that content-based centrality is still related to other centrality metrics, especially in situations with poor caching performance.

Nevertheless, nodes classified by our approach outperform them when more popular content is placed in the fog, despite the possibility that such nodes might not be well placed in the network. On the other hand, the non-centrality based sociallyunaware resulted in the poorest performance in all topologies. Similarly, in the case without fog formation, i.e. noncollaboration resulted in poor performance with an overall success rate of less than 20%.

VI. CONCLUSIONS AND FUTURE DIRECTIONS

Our results show that content placement in ICN can be efficiently managed by forming fogs allowing nodes to collaboratively cache at high content-based centrality nodes. "Content" based centrality outperforms the node-centric approach to classify nodes for distributed caching.

In this paper, we targeted the content placement problem at caches near the network edge as in a fog network. To do so, we suggest to exploit graph properties to identify the suitable nodes for caching, however, unlike typical node-centric centrality scheme, we first presented a new popularity-aware content-based centrality scheme, P-CBC, where the content popularity and the number of paths to all content, instead of nodes, counts towards the node centrality. Then, we proposed an algorithm for collaborative content placement in the fog, where the nodes place popular content at high centrality nodes, followed by placing the remaining content with decreasing popularity at nodes with decreasing centrality score, according to a replication rule which allows to compute our proposed centrality without knowing the actual content placement. The benefits of P-CBC are evaluated via simulations on 2, 986 nodes, three different topologies along varying three content replication levels. Results show that nodes in the fog based on our centrality outperforms, in terms of cache hit rate and success rate, existing centralities, non-centrality based and non-collaborative caching approaches.

Future work includes moving to dynamic topologies and study the impact of mobility on P-CBC. We plan to use it for content retrieval where the user interests are forwarded to high centrality nodes.

Figure 2 :

 2 Figure 2: Average cache hit rate achieved by P-CBC on three different topologies with three content replication ratios.

3 Figure 3 :Figure 4 :

 334 Figure 3: Hit rate comparison for centrality-based (P-CBC, CBC (no popularity), Degree, Closeness, Betweenness, Eigenvector), non-centrality based or social-unaware (LRU) and non-collaborative (no fog) based caching.

Figure 5 :

 5 Figure 5: Success rate comparison for centrality-based (P-CBC, CBC (no popularity), Degree, Closeness, Betweenness, Eigenvector), non-centrality based or social-unaware (LRU) and non-collaborative (no fog) based caching.