Meryem Marzouki

Rikke Frank

Joergensen Reshaping

Rikke Frank Jørgensen

Reshaping the Human Rights Legacy in the Online Environment

From the early debates in the mid-1990s on the human rights implications of internet use, to the new momentum created by Edward Snowden's revelations of State surveillance in 2013, the issue of human rights online has received considerable attention over the past 20 years. There is by now common agreement that human rights apply online as they do offline; yet in practice, the modalities of the online realm provide significant challenges to human rights protection, many of which remain largely unexplored. Moreover, in the course of the above-mentioned efforts, some so-called 'new digital rights' have been advocated, such as the "right to internet access" and the "right to be forgotten". This paper explores the background of such proposals and how they have unfolded over time and across various arenas and circumstances. It analyzes how different actors (states, intergovernmental organizations, civil society, technical community, internet companies) have been framing and advancing these proposals through either political contention or coalition of interests around key international events and momentum, paying particular attention to the role and influence of WSIS and post-WSIS multi-stakeholder internet governance processes. In conclusion, the paper discusses the broader human rights implications of these developments. It argues that (1) they reflect the strong impact of the specifics of the online environment on the very concept of fundamental rights, and (2) they may constitute threats to the universality and indivisibility of all human rights and undermine the level of human rights protection online.

Introduction

International policy discourses related to the digital environment increasingly reference human rights and fundamental freedoms. From the early debates in the mid-1990s on the human rights implications of internet use, to the new momentum created by Edward Snowden's revelations of State surveillance in 2013, the issue has received considerable attention over the past 20 years.

At the global and regional levels, a historical perspective identifies several milestones in this global evolution. To name a few of these milestones: the early WSIS steps (2002-2005), with the "Right to Communicate" vision opposed to one that promoted the identification of practical ways to realize and advance existing human rights in the online environment, with a special emphasis on the indivisibility and interdependence of all human rights; the IGF steps (2006-present), with different stakeholders, on their own or through multi-stakeholder dialogues, working on various initiatives aimed at strengthening the human rights perspective in internet policy; the UN Human Rights Council (HRC) and Universal Periodic Review (UPR) proceedings where, since 2012, global NGO coalitions specializing in human rights on the internet closely cooperated with the (former) UN Special Rapporteur on Freedom of Expression who was very attentive towards internet-related issues and the need to address internet policy from a human rights perspective. These efforts, together with some government led actions dedicated to freedom of expression and privacy in particular, have resulted in the adoption of the first two Resolutions focusing specifically on human rights protection on the internet, adopted at the UN Human Rights Council in 2012 [START_REF]Human Rights Council, resolution 20/8, The promotion, protection and enjoyment of human rights[END_REF] and 2014 2 , as well as the first two Resolutions on Privacy in the Digital Age, adopted at the UN General Assembly in 2013 [START_REF] Assembly | resolution 68/167[END_REF] and 2014 4 .

In parallel, the usual process of national and regional (e.g. in the European Union) internet policy making has been going on through legislation, jurisprudence and regulation, often independently of the global discussions and sometimes even detached from the concern raised by some Europeans governments and other institutions in global governance arenas. Likewise, civil society groups and other actors have pursued (sometimes in coordinated efforts) the call for the protection and enforcement of human rights standards in the online domain through advocacy, lobbying, and campaigning, locally as well as regionally.

Finally, the emergence of internet giants with the advent of web2.0 and social networking applications and services has raised the fundamental challenge that the conditions for public and private life on the internet depend on infrastructure and platforms governed by the private companies that provide them. In addition to the daily use of such platforms for a major part of our activities, activists' use of social media to organize and publicize their actions to fight authoritarian regimes and/or socio-economic inequalities, have proven to be a common feature among otherwise very different cultural backgrounds, political contexts and associated issues.

There is by now common agreement that human rights apply online as they do offline, yet in practice the modalities of the online realm provide significant challenges to human rights protection, many of which remain largely unexplored. Moreover, in the course of the above-mentioned efforts, new "digital rights" have been suggested and advocated by different groups and coalitions, such as the "right to internet access" seen as a necessary precondition to democratic participation; or the "right to be forgotten" in the field of privacy and personal data protection.

Focusing on these proposed new "digital rights", this paper explores the background of such proposals and how they have unfolded over time and across various arenas and circumstances. It analyzes how different actors (states, intergovernmental organizations, civil society, technical community, internet companies) have been framing and advancing these proposals through either political contention or coalition of interests around key international events and momentum, paying particular attention to the role and influence of WSIS and post-WSIS multistakeholder internet governance processes. In conclusion, the paper discusses the broader human rights implications of this development, arguing (1) that it reflects the strong impact of the specifics of the online environment on the very concept of fundamental rights, and (2) that it may constitute threats to the universality and indivisibility of all human rights and undermine the level of human rights protection online.

Human Rights and Communication Rights: An everlasting controversy?

"We […] declare our commitment to a common goal of building a people's internet from below and beyond borders: an internet that works in the public interest and solidarity, where control is in the hands of people; an internet based on human dignity, equality, social justice, freedom and people's communication rights". This sentence opens the 'Tunis Resolution5 ", adopted by the participants of the Workshop "Organizing an internet Social Forum -A Call to Occupy the internet", held in Tunis as part of the World Social Forum 2015. It is the most recent reference to date to the concept of 'Communication Rights' in an adopted document that, interestingly enough, does not make a single reference to 'Human Rights' as the existing international normative framework defined by the United Nations Bill of Rights (though it was indeed mentioned in the initial 'Call For An internet Social Forum6 ', which led to the organization of this first workshop as a first step towards the internet Social Forum.

Moreover, the Workshop that led to the adoption of this 'Tunis Resolution' was mainly an initiative of the JustNet Coalition (JNC), one of the civil society coalitions active in IGF and most recent related internet governance initiatives7 . Indeed, all 35 JNC organizational members are signatories of the Call, and constitute half of the overall signatories; furthermore, four of the indicated regional contacts are representatives of JNC organizational members, while the fifth is one of JNC individual members. When looking at JNC organizational members, the insider of WSIS and post-WSIS activities can easily identify some of the most prominent members of the 'Communication Rights in the Information Society' (CRIS) Campaign that played a major role during early WSIS steps, until the end of WSIS first phase in 2003 (CRIS, 2005).

Put together, both the framing of the 'Tunis Resolution' text and the identification of major players in the announced internet Social Forum ring a bell, reminding the main controversy related to human rights within civil society during WSIS first phase, that we identified and analyzed at that time (Marzouki and Jørgensen, 2004; Jørgensen and Marzouki, 2005). When adding the continuous confrontation8 of internet governance visions between (members of) the JNC and BestBits9 , another main civil society coalition active in the same post-WSIS circles, it becomes clear that we might soon observe a remake, ten or fifteen years later, of the same old controversy.

The description and analysis of various civil society components and theiragonistic as well as antagonistic -interactions in post-WSIS developments being beyond the scope and objective of this paper, we will only mention here some of their specific positions on one issue or another when relevant. However, the controversy related to human rights needs to be elaborated upon when analyzing internet governance and the reshaping of global human rights legacy. This controversy finds its roots back in the late 1960s, with the proposal of a right to communicate. The right was first suggested by Jean d'Arcy -a pioneer in French and European television -in an attempt to link human rights with recent (at that time) developments in communication technology, in particular satellite communication. Although a precise definition of the right to communicate was never provided, the basic idea was that Article 19 of the UDHR was too narrow to encompass the implications of technological developments, and that the right to communicate should encompass more extensive possibilities, so that electronic communication would no longer be confined to the media elite.

Further attempts to define the right to communicate and its practical implementation, most notably in terms of satellite spectrum regulation, led to heated debates at the UNESCO in the mid-70s, with the attempt to promote a so-called "New World Information and Communication Order" (NWICO) (CRIS, 2005: Chapter 2; McKenna, 2011: Chapter 6; Frau-Meigs et al., 2012). At end of this controversy, supporters of the right to communicate were opposed to defenders of the "free flow of information" doctrine, and it finally ended with ideological clashes between the East and the West (that was during the cold war) and between the North and the South (with the Non Aligned Movement, in particular). When the McBride Commission released its report ("Many Voices, One World") in 1980, attempting to define the conditions for realizing a right to communicate, unresolved ideological differences led the US and the UK to withdraw from UNESCO.

With the early steps (2001-2002) of the World Summit on the Information Society (WSIS) came a resurgence of the right to communicate, this time at the initiative of the "Communication Rights in the Information Society" (CRIS) Campaign. The CRIS campaign proposed the idea of a right to communicate -in response to, among others, concerns about media concentration -to the civil society plenary formed around WSIS, aiming for general support by civil society. Like in the old NWICO conflict, the idea was opposed in the name of the free flow of information, this time by the Media Caucus. It also faced contradiction from the Human Rights Caucus. The Human Rights Caucus shared the concerns raised by the CRIS campaign, yet disagreed on the means to resolve them. Rather than introducing new human rights, the Human Rights Caucus iterated the need to translate existing human rights to the digital environment, and to identify practical ways of realizing and advancing them, with emphasis on the indivisibility and interdependence of all human rights.

The debate within civil society on this issue at WSIS was resolved by the end of the first WSIS phase. At the "World Forum on Communication Rights10 ", it was agreed that the call for the effective enjoyment of a right to communicate needs not invent new legal standards, but should rather concert in the call for enforcement of existing human rights standards. This shift was explicitly acknowledged by the CRIS Campaign itself: "the use of the term "communication rights", since it is in the plural form, implicitly points towards existing human rights that relate to communication, and away from promoting a new formal right to communicate, in the singular, in international law. The emphasis shifts subtly to realizing the existing communication rights on the ground, not on establishing a new right under international law" (CRIS, 2005: p. 19).

Although this main controversy has largely evolved since then (Padovani et al., 2010; Jørgensen, 2013), especially through its reframing and reshaping taking into account the evolution of the technology and the economy as well as other global transformations, it is still underpinning most of internet governance visions and debates, including the most recent ones. One of the strongest sign of its persistence is the foundation of the JustNet Coalition in 2014, as both a specific political stand and a detachment move from the BestBits coalition, notwithstanding BestBits' claim since its creation in 2012 to "not aim to present a single solution for ratification by the assembled groups, but rather to offer an open space where each group can present and advocate for the initiatives that they believe offer the best positive agenda for advancing broadly shared civil society interests in internet governance 11 ".. There is no doubt that the internet Social Forum, expected to be held early 2016, will confirm the divergences. In the mean time, such controversies keep flourishing through debates on specific issues, such as the "right to internet access", suggested and advocated by different groups and coalitions as a new "digital right".

internet Access: A Right In Its Own?

In parallel to the WSIS debate on a right to communicate (which mainly took place amongst civil society actors), was a related but less politicized debate on internet access. In the early years of this debate, it mainly referred to technology infrastructure and the fact that the majority of the world population remains without such access, often referred to as the "the digital divide" although this is a highly contested notion, especially as it is trying to find technological solutions to problems that are essentially socioeconomic (Parayil, 2005; Pieterse, 2006; Wildermuth, 2010). Interestingly, in a context where the main economic actors were not anymore 6 the major media corporations but rather the big internet intermediaries, this debate around internet access was framed differently from the right to communicate.

Most notably, it had a more narrow and technical perspective on internet access, addressing it primarily as a matter of infrastructure (or lack hereof). This is not surprising since one of the main UN bodies dealing with WSIS was the ITU (tasked with telecommunication infrastructure), and since many government delegates struggled to make sense of the exact content of the information society Summit. Dealing with obvious inequalities in access to infrastructure including how to "roll out" more infrastructure was a concrete and less controversial topic than the socioeconomic dynamics underlying these global differences. The lack of internet access for a majority of the world's population has since WSIS spurred a number of intergovernmental initiatives such as the International Telecommunications Union's 'Connect the World' initiative that seeks to provide access to ICT to some one billion people living in remote areas by 201512 . Moreover, it continues to be on the agenda of every internet Governance Forum (IGF13 ). It is, however, increasingly addressed as a broader theme, paying attention to the many factors that enable participation in the digital domain.

More recently, this debate has developed into proposals for a human right to internet access. The definition of such a new right is rather fuzzy, and not well definedneither in concept nor scope. Global civil society networks such as the Association for Progressive Communication (APC) had started to frame internet access as a human right in their work on internet rights during the WSIS process, producing in 2006 the "APC internet Rights Charter14 ". The 2006 APC Charter claims not only for a "right to access", but for some even more unexpected "rights", such as "the right to open architecture", or "the right to the internet as an integrated whole". These proposed "rights" are neither precisely defined in the 2006 Charter, nor is it explained how they derive from international human rights standards. Although they are added to some of the established human rights, it becomes understandable why the framing of "internet rights" -rather than human rights -was preferred for this collection of claims, wishes or principles. This initial work was further elaborated in the process of developing the first version of the "IRPC Charter of Human Rights and Principles on the internet15 ". The Charter was developed from 2009 onwards by the internet Rights and Principles Coalition (IRPC), a multi-stakeholder coalition formed at the IGF (Franklin, 2013: Chapter 5). Its first version was released by end 2010. The chosen approach, as recommended by the group of human rights experts having provided the first draft 16 , was to start from the UDHR, and to keep as close as possible to its defined rights and other provisions (only some obviously irrelevant in the context, such as that of Article 16 for instance, were not included). The Charter stresses the transformative nature of the internet not only to enable individuals to exercise their right to freedom of expression, but also to enjoy a range of other human rights, including the right to health, the right to education, the right to gender equality and so forth. It also goes beyond the rights stipulated in the international Bill of human rights, to incorporate, for instance, provisions on the right to development. The IRPC Charter does stipulate in its Article 1 a "Right to access the internet". However, its provisions make it clear how it is intended: "access to and use of the internet is increasingly indispensible for the full enjoyment of human rights, including [main UDHR rights listed]".

In 2011, the debate on internet access as a human right was fueled by a number of media outlets that mistakenly claimed that Frank La Rue (at the time UN Special Rapporteur on the promotion and protection of the right to freedom of opinion and expression) had declared such a right. In fact, what La Rue had recommended was to make universal internet access a priority for all states 17 . The rapporteur appreciated that this could not be instantly achieved because of, for example, deficient electricity access 18 . Nevertheless, States are positively obliged to promote or enable the means necessary for individuals to exercise their freedom of expression. Also, once the infrastructure has been established, policies and strategies should be adopted which make the internet widely available, accessible and affordable for all. Similarly, the first UN "Resolution on the promotion, protection and enjoyment of human rights on the internet" adopted in July 2012 19 does not recognize a right to internet access. Nor does it prescribe any universal service provision, or suggest revising existing peering and transit agreements in order to make internet access universally affordable. The resolution does, however, stress the freedom to access the internet and includes a "call upon all States to promote and facilitate access to the internet and international cooperation aimed at the development of media and information and communication facilities in all countries". Likewise, the UN Human Rights Committee in its general comment on freedom of expression considers that internet-based modes of expression are protected and that States should accordingly adopt all necessary steps to ensure access to the internet 20 .

In a highly debated newspaper article from January 2012, Vincent Cerf -a key figure in the technical community around internet governance -argued against a human right to access the internet. Cerf's main concern is that technology is an enabler, not a right in itself: "There is a high bar for something to be considered a human right. Loosely put, it must be among the things we as humans need in order to lead healthy, meaningful lives, like freedom from torture or freedom of conscience. It is a mistake to place any technology in this exalted category 21 ". In 17 See Paragraph 86 of Report of the Special Rapporteur on the promotion and protection of the right to freedom of opinion and expression, Frank La Rue, A/HRC/17/27 (16 May 2012). Available at: http://www2.ohchr.org/english/bodies/hrcouncil/docs/17session/A.HRC.17.27_en.pdf 18 Ibid. Paragraph 66 19 UNGA Resolution A/HRC/20/L.13, adopted in June 2012. Available at: http://daccess-dds-ny.un.org/doc/UNDOC/LTD/G12/147/10/PDF/G1214710.pdf 20 See Un Human Rights Committee General Comment No. 34 on Article 19: Freedoms of opinion and expression. Available at : http://www2.ohchr.org/english/bodies/hrc/docs/gc34.pdf response, proponents of this new right argued that access to the internet is a precondition for enjoying a number of other human rights and should therefore be considered a right on its own merits 22 . In line with this, a BBC survey amongst 27 000 people in 26 different countries in 2010 showed that four out of five believed internet access to be a basic human right 23 .

Most recently, the Council of Europe's Parliamentary Assembly have adopted a resolution on the right to internet access. It iterates that everyone shall have the right to internet access as an essential requirement for exercising rights under the European Convention on Human Rights. In consequence, "States should recognize the fundamental right to internet access in law and in practice" 24 . On a more cautious note (and practically at the same time), the Council of Europe´s Committee of Ministers adopted a Recommendation on a Guide for Human Rights of internet users 25 . Concerning access to the internet, this is addressed in the first section of the Guide (together with the principle of non discrimination), but not as a right in its own merit. As stated in the presentation to the Guide: "The guide does not establish new human rights and fundamental freedoms. It builds on existing human rights standards and enforcement mechanisms". This formulation derives from the terms of references for the committee of experts set up to develop the Guide, and was a requirement from the Council of Europe member states: contrarily to the Parliamentary Assembly, member states did not want to engage in the politically sensitive process of defining new human rights, especially in an instrument carrying a higher level of commitment than a Resolution.

A final example of developments around internet access relates to industry-driven initiatives such as Facebook's internet.org project that aims "to connect the two third´s of the world that doesn't have internet access" 26 . The initiative is a partnership between the social media platform and a number of ICT companies such as Nokia, Ericsson and Samsung, and provides users with a Facebook-defined internet platform. When presenting the project, Facebook founder Mark Zuckerberg asserted [START_REF] Zuckerberg | Is Connectivity a Human Right?[END_REF] : "connectivity is a human right". Since its launch in 2013, the initiative has been criticized by civil society (not least in India and Brazil) for violating net neutrality and for Facebook's role as gatekeeper in determining what websites users of internet.org may access. In particular, a number of NGOs sent an open letter [START_REF]Open Letter to Mark Zuckerberg Regarding internet.org, Net Neutrality, Privacy and Security[END_REF] to Facebook to express their opinion on this initiative. As one of the signatory organizations commented, they considered that "internet.org comes with too many strings attached 29 ". Following these critiques, Facebook rebranded 30 its initiative in September 2015 into "Free Basics", and added some new services to it.

In sum, while a right to internet access has been widely promoted and debated, it seems fair to conclude that a (positive) human right to access the internet is not established under international human rights law (Tully, 2014; Land, 2013). Rather, a negative state obligation (not to interfere with the means of communication, nor the content) is established as part of freedom of expression (Hopkins, 2010; See also ECHR case-law). For example, critique of government interference with individuals internet access routinely features in State Party reports, Concluding Observations and General Comments emanating from the UN human rights committees (see the many examples highlighted in Tully 2014). Also, as argued by La Rue and others giving effect to the right to freedom of expression imposes a positive obligation upon States to promote and facilitate universal internet access 31 . In this sense, the human rights framework may help rectify deficient internet access and ensure greater equality for deprived groups, thus using the moral authority of the human rights discourse to commit states to prioritize this area (Tully, 2014: p. 189).

Arguably, internet access is an enabler for most -if not all -human rights, and thereby relates to societal participation in the broadest sense. As such, internet access has a range of political, economic, social and cultural dimensions. Moreover, its importance in relation to a number of existing rights has been widely recognized by the UN human rights system. In contrast, the call for a new human right to access the internet seems unlikely to succeed. The fundamental rights that make up international human right law was formulated and agreed upon at a specific point in time (post second world war), and many commentators have warned that if those rights were to be renegotiated in the political climate of today, they would be weakened rather than strengthened. Moreover, since the importance of internet access and internet freedoms increasingly is recognized and accommodated as part of existing freedoms and rights related to opinion, expression, privacy, association, cultural participation, etc., the real challenge seems rather to be the effective realization of these rights. In consequence, as access becomes more widespread, the debate may turn back to the themes raised by the proponents of the right to communicate, such as whether or not the internet is enabling a more diverse and decentralized public debate and participation. Also, one should be cautious by industry attempts to use the global inequality to promote platform-specific internet access as exemplified above, for instance by the internet.org project. Rather than promoting human rights such initiatives may lead to disempowerment and capture of said communities into specific platforms of content, as opposed to an open internet. Moreover, the US Government announced in late September 2015 to the UN General Assembly its Global Connect Initiative 32 . In a 30 See Facebook announcement at : http://newsroom.fb.com/news/2015/09/update-to-internet-org-freebasic-services/ 31 Joint Declaration on Freedom of Expression and the internet by the UN Special Rapporteur on Freedom of Opinion and Expression, the OSCE Representative on Freedom of the Media, the OAS Special Rapporteur on Freedom of Expression and the ACHPR Special Rapporteur on Freedom of Expression and Access to Information, 1 June 2011, at para 6. Available (inter alia) at: http://www.oas.org/en/iachr/expression/showarticle.asp?artID=849 32 See the USG announcement at : http://www.state.gov/r/pa/prs/ps/2015/09/247374.htm nutshell, the initiative consists in making internet access a top priority of all US aid and development agencies worldwide operations, and of engaging international development banks to adopt the same objective. Most notably, the USG statement explicitly mentioned that it "will work with private industry which has created innovative solutions to connect people in remote areas". The implications of these private initiatives and public-private partnerships, including how these developments may change the culture of human rights from a zone of contestation ("power regulator") to a realm of industry-driven Corporate Social Responsibility (CSR) initiatives, may have significant consequences in the long run. The corporate framing of human rights may impact not only on specific rights such as freedom of expression and information, but may have a broader impact on the effective protection of these rights in the online realm.

Introducing a Conflict of Rights: To Be Or Not To Be Forgotten?

The "right to be forgotten" (RtBF) (or "right to oblivion" as it is sometimes referred to) has been one of the most contentious and debated human rights issues in the past five years, dividing proponents of online privacy and freedom of expression, respectively.

The framing of a right to be forgotten started in Brussels amongst European policy makers and attached experts around 2009 with the publication of Viktor Mayer-Schönberger´s book "Delete -The Virtue of Forgetting in the Digital Age" (2009). In January 2012, the European Commission published the Proposal for a Regulation on the Protection of Individuals with Regard to the Processing of Personal Data and on the Free Movement of Such Data ("GDPR"), which updates the current Data Protection Directive from 1995 (95/46/EC). The GDPR is expected to enter into force in 2016, and will instantly become law throughout the European Union. The GDPR has been widely interpreted as to provide all European Union citizens a "right to be forgotten", by giving the individual a right to have his or her personal data removed from the web. This interpretation is based on Article 17 of the initial GPDR proposal 33 providing for a right for data subjects to request erasure of their personal data as well as the abstention from further dissemination. Article 17 establishes the criteria for when a data subject can have personal data removed, data controllers' obligation to erase links to third-party websites, and how to exercise that right. While this initially proposed Article 17 is explicitly entitled "Right to be forgotten and to erasure", the extent to which it actually provides for a new right and corresponding duties has been contested amongst activists, scholars and regulators. As stressed by van Hoboken (2014), when examining the EC proposal for the data protection reform from January 2012, arguably, there is no such thing as a new right to get data deleted in the proposed Article 17.

Later in the process, European Parliament amendments removed the 'right to be forgotten' from the text but seem to strengthen the right to erasure in some 33 See EC Communication COM(2012)11 of 25 January 2012 on a "Proposal for a REGULATION OF THE EUROPEAN PARLIAMENT AND OF THE COUNCIL on the protection of individuals with regard to the processing of personal data and on the free movement of such data (General Data Protection Regulation)", available at: http://ec.europa.eu/justice/dataprotection/document/review2012/com_2012_11_en.pdf respects. For instance, the right to have links, copies or replication of data deleted has been more clearly stipulated and has been included in Article 17 (1) along with an additional ground to obtain the right to erasure, namely in case of a decision by court or regulatory authority based in the Union 34 .

Since the introduction of the GDPR proposal, the "right to be forgotten" has been subject to intense public debate in Europe as well as in the United States, and concern has been raised as to its negative impact on freedom of expression. Similar to the data protection directive, the GDPR strives to balance privacy and freedom of expression by presenting freedom of expression as a limitation on the right to have personal data erased. According to Article 80(2) of the GDPR proposal, it is up to each member state to determine what to include in the freedom of expression exception after the GDPR enters into force.

On this backdrop, the decision of the Court of Justice of the European Union (CJEU) on Google Spain v. AEPD in May 2014 35 was seen by many commentators as reading a "right to be forgotten" into the currently in force Data Protection Directive. The court's decision recognized the right of a Spanish citizen to have personal data about his insolvency de-referenced so that this information would not appear in response to a search for his name in a search engine. The Court classified Google as a controller of personal data and thereby subject to the Data Protection Directive and responsible for removal of the information.

The Google Spain decision led to a flood of reactions in the media, particularly in the United States 36 . In the public debate, the Google Spain Decision has been widely referred to as the right to be forgotten ruling, and its implications for freedom of expression and access to information intensively discussed amongst both industry, regulators, academics and civil society.

Former EC Vice-President Viviane Reding have publicly defended the right to be forgotten, both when introducing the GDPR 37 and in response to the Google Spain decision 38 ; newspapers around the world have stated that in Europe people will now be granted the right to have their data deleted 39 , and it has turned out to be one of the most debated topics in scholarship related to the reform of the European data protection regulation 40 . In his Opinion dated 14 January 2011, the then European Data Protection Supervisor, Peter Hustinx, has stressed that in the online domain economic forces work against the individuals' right to privacy, hence there is a need to strengthen the request for data deletion. Others have argued that the GDPR and the Google Spain ruling merely updates principles that are already part of the European data protection regime, and does not introduce substantially new rights.

Generally speaking, there is strong support for a right to be forgotten in Europe. A European Commission study concluded that seventy-five percent of Europeans favor such a right 41 .

In contrast, the right to be forgotten has been ridiculed and criticized by the involved industry (Google and other search engines), as well as a wide array of US scholars, academics, and free speech advocates. Commentators have warned that the right to be forgotten will lead to censorship of the internet because individuals can request search engines or websites to erase personal data, which may rewrite history [START_REF]The Right To Be Forgotten Will Turn the internet into a Work of Fiction[END_REF] . In a widely cited blog post from March 2011, Peter Fleischer, chief privacy counsel of Google, notes that the right to be forgotten, as discussed in Europe, covers three separate categories, each of which proposes progressively greater threats to free speech [START_REF] Peter | s blog post. Foggy Thinking About the Right to Oblivion[END_REF] . Others argue that if content becomes less searchable on the internet, it will "derogate the role of counter-speech" and "disrupt the natural process of communication" (Larson, 2013). As stated by some scholars, the right to be forgotten should not subordinate freedom of expression because free and open public access enables citizens to discuss and share information about society (Rustad and Kulevska, 2015: p 373).

In response to the ruling, Google have established an Advisory Council on the right to be forgotten, and have held meetings in a number of European cities to raise their concerns. An important part of the critique pertain to the enforcement of the right, stressing that the CJEU ruling provides no guidance as to how data controllers are to determine when data that is the subject of an erasure request is no longer necessary or where there is no legal basis for retaining it. Consequently, the burden falls on the data controller to determine those factors, placing Google and other search engines in the position of gatekeepers that determine which data deletion requests should be granted and which should be denied.

In November 2014, the Article 29 Working Party Guidelines published Guidelines to address this concern 44 . The Guidelines provide recommendations to European Data Protection Authorities on how they should address complaints received by individuals after Google denied them their de-referencing request; On 18 June 2015, the Article 29 Working Party published a first evaluation survey 45 of such complaints. In its report of February 2015 46 , Google's Advisory Council on the right to be forgotten recommended more transparency, underlining that data controllers should be as transparent as possible by providing anonymized and aggregated statistics as well as the process and criteria used in de-referencing decisions. Beyond the benefits to users that request content removed and the wider public, transparency might help search engines shape implementation guidelines and reveal aspects of the legal framework that require clarification. Another challenge is that the right to delete may vary depending on the EU member state, or between EU and other countries, in case the right to be forgotten will eventually be expanded beyond EU member states. As a matter of fact, a first conflict recently arose between the CNIL (the French Data Protection Authority and current Chair of the Article 29 Data Protection Working Party) and Google. In view of a global extension of the right to be forgotten, the CNIL ordered Google to apply de-referencing on all domain names of the search engine, not only restricting its application to search results available in the European domain 47 . On July 30, Google expressed its disagreement with the CNIL's interpretation of the CJEU ruling, asking it to withdraw its formal notice 48 , arguing against such a "troubling development that risks serious chilling effects on the web". On 21 September 2015, the CNIL rejected 49 Google's request, which may lead to a financial sanction of a maximum of 150 000 euros against the company. Interestingly, Google's arguments to deny the application of the RtBF beyond the French jurisdiction are based on freedom of expression, freedom of information and the competence of jurisdictions, while the CNIL remains consistent with considering Google as a data controller, in line with the CJEU ruling.

In sum, the discourse against the right to be forgotten has primarily been driven by US scholars, free speech activists, Google and other industry actors. The Google Spain ruling has been framed as a threat to freedom of expression while its relationship to existing data protection regulation has largely been ignored in the public debate. This is not to say that the actual implementation of the decision is not problematic. From a rule of law perspective, it places private actors as judges of which content to remove from the public domain (de-referencing), and which to leave up. This form of privatized law enforcement is part of a more general trend towards "self-regulation", where the private actors in control of the internet's infrastructure and core services are tasked with enforcing public policy, without a public mandate. In practical terms, the task of assessing numerous deletion requests may lead to overbroad implementation, not least from less resourceful search engines. Also, as pointed to by the NGO European Digital Rights 50 , Google and other search engines already remove content, for example, when they enforce the US Digital Millennium Copyright Act -without similar freedom of expression concerns -and Google has even granted a "right to be forgotten" for victims of "revenge porn", without restricting its application to Europe 51 . Yet, the freedom of expression and rule of law concerns related to these practices have not received similar attention in the public debate. freedom of expression. Yet, one may fear for future developments and the lobbying by some states. One challenge relates to the fuzziness of the notion and the potential expansion of the right. In France, for example, some members of Parliaments have demanded that this right be extended to a right to delete content that others have published on one user, especially young users. This would mark a slippery slope towards privatized censorship. If the intention is primarily to extend the data subject rights towards a right to informational self-determination, the Council of Europe approach may be a better way forward -as exemplified with the modernization process of Convention 108, including new provisions to strengthen the rights of the data subject 52 .

One of the main risks with unclear and politicized notions such as the right to be forgotten is that it may lead to a change of paradigm, especially in the current context of big data, data mining, and profiling. In this new paradigm, limits on data collection based on purpose would no longer be the default, nor would the principle of data minimization. Rather, the default would become the collection of large amounts of data, with some provisions as a guarantee for control of their use, to the extent that this control can still be reasonably exercised. Although this may seem like an exaggeration, the right to be forgotten can become the fragile companion, or the crutch of a "right to collect and use big data". At present, this development is promoted both from the industry that strive on big data, and from experts and some data protection authorities (including inside the EU) that advocate for replacing restrictions on data collection with limitations on data use (Mayer-Schönberger and Cukier, 2013). Such a trend might well undermine the principle of purpose limitation, which is one of the cardinal principles of data protection in Europe.

Conclusion

When considering some of the broader human rights implications of the proposals and developments outlined here, and despite the differences in character and context of the considered examples, some interrelated tendencies seem to emerge, or to confirm trends previously identified in the literature on self-or co-regulation (Frydman, 2004; Marzouki, 2008).

First, we see a shift in how human rights are envisaged and debated, from the traditional focus on state obligations and state enforcement (hard law) to an increasing involvement and call upon private companies to take a role in the realization of some human rights (e.g. through charity actions, participation in soft law development, and through codes of conducts and other corporate social responsibility initiatives). The human rights language is being used (captured) by a variety of actors to promote specific interests, often with limited reflection on human rights as a set of international legal norms, with inherent zones of conflicts (e.g. protection of individuals against abuse of power, commitments to certain standards in society). This shift in the human rights discourse from state obligations to corporate initiatives seems to reflect the nature of the online environment with private actors in control of core infrastructure and services, yet it is extending and its implications for the protection of individuals is troublesome and have not been 52 See http://www.coe.int/t/dghl/standardsetting/dataprotection/modernisation_fr.asp subject to sufficient substantial analysis yet.

Second, the post WSIS era has witnessed a regression of the concerns related to socio-economic and development (or collective) rights, and an increasing focus on civil and political rights, particularly freedom of expression and privacy, i.e. individual rights (Brousseau and Marzouki, 2012). As mentioned, the legacy of the Universal Declaration of Human Rights is among others due to its specific place in history and the way it stresses the universality and interrelation between civil, political, social, economic, and cultural rights. Increasingly, different actors "pick up" "their" right of interest, with limited attention to the overall framework and the interdependence between the full architecture of rights. Also, the idea of inventing new rights (as with the right to internet access) seems to ignore that Conventions are living instruments, and that their standards are expected to be translated into current situations, taking into account technical and socio-economic developments.

Considered as a whole, these observations indicate a profound redefinition in the digital sphere, mainly through procedural transformations of existing legislation and regulation, of the legacy of the Universal Declaration of Human Rights. In future work, we wish to explore in more details the hypothesis that this transformation is closely related to the fact that the internet is governed mainly by private actors, that sometimes conflict with state regulations (e.g. in the field of data protection as analyzed here in the case of the right to be forgotten), but other times converge with them as to the means and methods (e.g. through big data mining, algorithmic regulation), and objectives (e.g. profiling and targeting behaviors).

See http://internetsocialforum.net/isf/?page_id=832

See http://internetsocialforum.net/isf/?page_id=848

Founded in February 2014, the JNC introduces itself on its website as "a global network of civil society actors committed to an open, free, just and equitable internet". See http://justnetcoalition.org/.

As their exchanges on internet governance mailing lists (including their own ones) attest.

The Bestbits coalition describes itself as "an inclusive network of key civil society organizations from across the world, who come together to highlight their various initiatives, and foster mutual learning and broader engagement", see http://bestbits.net/organizer/best-bits/. It started its activities in 2012.

The Forum was co-organized by, among others, the CRIS campaign and the Human Rights Caucus as a side event to the WSIS Summit in Geneva in 2003. See the web site at: http://www.communicationrights.org/

See the International Telecommunication Union, Connect the World, available at: www.itu.int/ITU-D/connect

13 See http://www.intgovforum.

org 14 See https://www.apc.org/en/node

/5677/ 15 See http://internetrightsandprinciples.org/site

/charter/16 Especially since some of them directed or contributed to a previous effort of translating human rights into the information society context[START_REF] Jørgensen | Human rights in the global information society[END_REF]

This Op-Ed published by Vint Cerf in the New York Times on 4 January 2012 is available at: http://www.nytimes.com/2012/01/05/opinion/internet-access-is-not-a-human-right.html


Mélanie Blazère

A variant of the spectral clustering method using 1 -penalty to promote sparse eigenvectors basis

Keywords: Spectral clustering, community detection, eigenvectors basis, 1 -penalty

The spectral clustering method is one of the most well-known graph clustering algorithm, that is used in a wide range of fields and applications. In this paper, we propose a variant of the spectral clustering algorithm, called 1 -spectral clustering. This procedure does not require the use of k-means to cluster the nodes of the graph, but directly estimates the indicators of the communities by computing a specific eigenbasis using 1 penalty.

Introduction

Since many systems of various kinds can be represented as networks, graphs play a central role in complex system [START_REF] Mark | Modeling social networks from sampled data[END_REF], [START_REF] Steven | Exploring complex networks[END_REF], [START_REF] Mark Ej Newman | The structure and function of complex networks[END_REF], [START_REF] Albert | Statistical mechanics of complex networks[END_REF]. Fields of application are many and various, ranging from mathematics (graph theory, combinatoric problems) to physics (systems of particles [START_REF] John | Neural networks and physical systems with emergent collective computational abilities[END_REF]), sociology (social networks [START_REF] Mark | Modeling social networks from sampled data[END_REF]), marketing (consumers preferences graphs), informatics (decision trees, combinatorial optimization, World Wild Web [START_REF] Pastor | Evolution and structure of the Internet: A statistical physics approach[END_REF]) or biology (neural, proteins networks, genes [JTA + 00]). In biology, there exists a lot of applications [MLF + 09], [START_REF] Andy | Gene network interconnectedness and the generalized topological overlap measure[END_REF],[GA05],[ZH + 05],[DHJ + 04], [START_REF] Michael Z Man | Evaluating methods for classifying expression data[END_REF], just to name a few.

Community detection is an important task for complex networks, that can help to understand the functional modules on the whole network. Community structures are believed to play an important role in the functioning of the complex systems modeled by graphs, so that detecting theses structures is of the highest importance. There exists different ways of defining community structures. The heuristic one corresponds to groups of nodes that are densely connected with sparse connections in between [START_REF] Girvan | Community structure in social and biological networks[END_REF], [START_REF] Mark | Finding and evaluating community structure in networks[END_REF]. Among different community detection methods based on graph structures, the spectral clustering method is currently one of the most popular and has been widely used in various fields. This method uses the eigenvectors of adjacency type matrices to cluster the nodes of a graph into a given number of communities. The nodes are not directly clustered but k-means is applied to the eigenvectors to detect the communities. If this method is so popular, it is mainly because spectral clustering is very easy to implement and easy to use. The computations are very fast and efficient, even for very large graphs. However, there is no guarantee to reach the best or most natural partitioning in general cases.

The purpose of this work is to present an alternative method to the classical spectral clustering for a specific random graph model, called 1 -spectral clustering. This is an alternative method in the sense that the partitioning of the graph is essentially based on the computation of the singular value decomposition of the adjacency matrix (or normalized adjacency matrix). The associated algorithm actually aims at finding a sparse basis of the eigenvectors of the adjacency matrix, starting from an initial basis that is not necessarily sparse but can be computed very quickly by any eigensolvers. This procedure turns out to solve an optimization problem of the form

argmin v∈S v 1 ,
where S is a subset in ∈ R n-1 based on some transformations of the initial eigenvectors of the adjacency matrix. The remainder of this paper is organized as follows. In Section 2, we introduce the notations. Section 3 is devoted to the presentation of the model we suggest to work on, i.e. a random graph model that is closely related to a stochastic block model. We actually assume that the observed graph results from a deterministic graph with an exact community structure, whose edges have been disturbed by Bernoulli variables. In Section 4, we recall the basic principles of the spectral clustering method. Then, we present a new method to estimate block membership of nodes, from the observation of the noisy graph. The performance of this procedure is strongly dependent on the perturbation of the adjacency matrix and more specifically on the Frobenius norm of the noise matrix. Some results on the expectation of the Frobenius norm of the noisy matrix (associated to the random model we consider) are given in Section 5. Finally, we study the performances of the suggested method on simulated data. Results are presented in Section 6. Experimental results indicate that this algorithm works well on simulated datasets and is effective at finding the good communities.

Graph notation

A graph G refers to a set of vertices and a set of edges. The nodes represent the individuals or objects and the edges the interactions and relationships between them. From a mathematical point of view, a graph G is a pair (V, E) where V is the set of vertices and E refers to the set of edges that pairwise connect the vertices [START_REF] Diestel | Graph theory[END_REF]. An edge e ∈ E that connects a node i and a node j is denoted by e = (i, j).

An important object associated to the graph is the adjacency matrix A = (A ij ) (i,j)∈V 2 . The element A ij represents the weight on the edge between node i and node j. For unweighted graphs, the adjacency matrix is defined by

A ij =
1 if there is an edge between i and j 0 otherwise .

If the graph contains

n nodes i.e. | V |= n, then A ∈ M n (R).
When the graph is undirected, A is a symmetric matrix. Its diagonal elements are equal to zero when there is no loop. The degree d i of a node i is equal to the number of edges incident to i

d i = n j=1 A ij .
The matrix D, called the degree matrix, contains the degree of the nodes d 1 , ..., d n on the diagonal and zero anywhere else

D =    d 1 0 . . . 0 d n    .
Given a subset of vertices C ⊂ V , we denote by C its complement, that is V \ C. We define the indicator vector 1 C ∈ R n as the vector whose entries are defined by

(1 C ) i = 1 if vertex i belongs to C 0 otherwise .
A subset C ⊂ V of a graph is said to be connected if any two vertices in C are connected by a path in C (sequence of vertices in C connected by edges that joined the two initial vertices). In addition, C is called a connected component if there are no connections between vertices in C and C. Non empty sets C 1 , .., C k form a partition of the graph if

C i ∩ C j = ∅ and C 1 ∪ ... ∪ C k = V .

Presentation of the model

There is no formal definition of what should be a community. But, there exists a consensus on the fact that it should refer to groups of vertices highly connected with sparse connections in between.

In this section, we assume that the observed graph, denoted by Ĝ, is actually a perturbed version of a graph G that has k fully connected components (called the communities). We actually assume that the observed graph Ĝ results from a deterministic graph with an exact community structure, whose edges have been perturbed by Bernoulli variables. We consider only undirected graph with no loops and we assume that the observed graph is connected (otherwise, it would be equivalent to work on each of the connected components of the graph).

Hereafter, observed quantities will be denoted by a hat.

The ideal graph

The ideal graph G is assumed to be the union of k complete graphs that are disconnected from each other. The number of vertices is n. The vertices are labelled from 1 to n. We allow the number of vertices in each subgraph to be different. We denote by s 1 , ..., s k (≥ 2) their respective size (of course k i=1 s i = n). To simplify and without loss of generality, we assume that the nodes {1, ..., n} are ordered with respect to their block membership, in increasing order with respect to the size of the blocks. In other words, the nodes in the smallest cluster are denoted by 1, ..., s1 and so on.

From a matricial point of view, the associated adjacency matrix A is block diagonal and has the following form

A =      A 11 A 12 . . . A 1k A 12 A 22 . . . A 2k . . . . . . . . . . . . A 1k A 2k . . . A kk      n ∈ S n (R)
where

A ij := 0 s i ,s j 1 ≤ i = j ≤ k and A ii := N s i -I s i =      0 1 . . . 1 1 0 . . . 1 . . . . . . . . . . . . 1 1 . . . 0      s i ∈ S s i (R), 1 ≤ i ≤ k.
I s i denote the identity matrix of size s i and N s i the square matrix of same size s i , whose entries are all equal to one. In other words,

A =                            0 1 . . . 1 1 0 . . . 1 . . . . . . . . . . . . 1 1 . . . 0      s 1 0 . . . 0      0 1 . . . 1 1 0 . . . 1 . . . . . . . . . . . . 1 1 . . . 0      s k                       n .
(1)

Perturbed version Ĝ of the graph G

We assume that we do not have access to this graph G. This is the case, for instance, if the graph has been inferred by estimating the dependencies between the vertices. We just observe a perturbed version of G denoted by Ĝ (some edges have been added between the communities and others have been removed within the communities independently with respect to a given probability). For instance, this perturbation may arise because of a partial knowledge of the graphs. This can be due to errors of measurement or to estimation noise (if the graph is estimated).

Let us detail what we exactly mean here by perturbations. Let  be the adjacency matrix associated to Ĝ. We assume that

 = A 2 ⊕ B (2)
where

• A ij = A 2 ⊕ B ij = A ij + B ij (mod 2).
• B is a symmetric matrix of size n, whose upper entries are realizations of independent Bernoulli variables

   B ij ∼ B(p) i.i.d., i < j B ii = 0 B ij = B ji .
B is therefore the adjacency matrix of an Erdos-Renyi graph G(n, p). We recall that an Erdos-Renyi graph G(n, p) has n vertices. The entries of its adjacency matrix are independent (up to the constraint that the adjacency matrix is symmetric) and equal 1 with probability p and 0 with probability 1 -p (except on the diagonal where the entries are deterministic and always equal to 0). A value of B ij equal to one means that the edge between nodes i and j is removed if the edge exists, or conversely that an edge is added if there was no edge before. To sum up

• If B ij = 1 and A ij = 1, we remove an edge between vertex i and j in G.

• If B ij = 1 and A ij = 0, we add an edge between vertex i and j in G.

• If B ij = 0 we do not change any thing on the initial graph.

The noise is independent from one edge to the other, so that a change appears with the same probability for all the edges. An edge is removed in a community with probability p and added between two communities with the same probability. So that, two nodes are connected with probability 1 -p if they belong to the same community and with probability p when they do not belong to the same community. We can easily generalize this model by considering different perturbation probabilities within and between each of the blocks. To simplify, in what follows, we keep the same value of p for all of the entries. The difference between purely random graphs and our model is that we do not assume that a group structure emerges by chance but because there exists an underlying structure. This structure can be based on a real physical or biological mechanism that have been significantly changed. Hence, the model is random but the underlying group structure is considered as fixed and is well defined. This is a kind of probabilistic-statistical model that is well suited to model graphs that have been inferred from observations. The model we consider is similar to the stochastic block-model, in the sense that the probability of an edge between two nodes depends only on the communities membership. But here, the membership of a node to a community is assumed to be fixed and not randomly assigned as in the stochastic block model. In the stochastic block-model, we have

P [A | τ ] = (i,j)∈V 2 i =j P [A ij | τ (i), τ (j)] = (i,j)∈V 2 i =j 1 -P τ (i),τ (j) 1-A ij ,
where τ is the random block membership function. This means that, conditionally to τ , the entries A ij of the adjacency matrix are independent Bernoulli random variables with parameter given by P τ (i),τ (j) (that depends on the community membership of the nodes i and j). The equivalent quantity of p i in a stochastic block model is somehow the nodes density of the communities. In our setting, there is no conditioning. The sizes of the communities are assumed to be fixed and equal to (s i ) 1≤i≤k . In addition, the number of nodes is kept fixed. But, it is the probability of an edge between two nodes that is supposed to vary. We implicitly assume that this probability p depends on a parameter and tends to zero when this parameter tends to infinity. For instance, we can imagine that the nodes of the graph represent features whose interactions have been estimated based on m observations, so that p -→ m→+∞ 0.

Because the graph and the adjacency matrix are equivalent, in what follows, we forget the graph and we only focus on the adjacency matrix.

Notations

Let us now detail some of the notations we will need later.

For l ∈ {1, ..., k}, let

M l = i ∈ [1, n] : l-1 r=0 s r + 1 ≤ i ≤ l r=0 s r . M l represents the indices of the nodes in community l. {M 1 , ..., M k } is a partition of [1, n], so that [1, n] = 1≤l≤k M l .
We also define

M c l = [1, n] \ M l = 1≤m≤k m =l M m .
For l ∈ {1, ..., k} and m ∈ {1, ..., k}, we define

J lm = M l ⊗ M m = (i, j) ∈ [1, n] 2 : i ∈ M l , j ∈ M m . {J lm } 1≤l≤m≤k is a partition of [1, n] 2 , so that [1, n] 2 = 1≤l,m≤k J lm .
We also define

J ll -= {(i, j) ∈ J ll , i = j} .
For any adjacency matrix F , we denote by D F the degree matrix associated to F . Its diagonal entries are denoted by d F i , where we recall that d F i = n j=1 F ij . The ideal adjacency matrix A given by Equation (1) has its degrees equal to

d A i := n j=1 A ij = s l -1, if i ∈ M l .
For l = 1, ..., k, let d l := s l -1. We have

D A = diag(d 1 , . . . , d 1 s 1 , ... d k , ..., d k s k
).

4 A new graph community detection procedure: l 1 -spectral clustering,

In this section, we suggest an alternative to spectral clustering to find the k underlying communities of a graph G from the observation of the noisy graph Ĝ. This new algorithm is based on the research of a "sparse" eigenvectors basis through l 1 minimization. We denote by C 1 , ..., C k the k connected components of G, that match the k communities. We recall that these connected components are sorted in increasing order of size, with size equal to s 1 , ..., s k .

Assumption

In addition to the number of communities, we assume that we know one representative for each of the community. By a representative, we mean a node belonging to this community. This assumption is not so restrictive compared to traditional spectral clustering where the number of communities is assumed to be known. In practice, the number of communities can be inferred from the structure of the graph or from the knowledge of the biological or physical process that drives the graphs. For instance, in genes networks, the groups of genes we search for often represent metabolism functions. These functions are a priori known and some genes implied in these metabolic functions have already been evidences by experiments. The aim is to cluster genes around these initial well-known ones to detect new genes and gain thereby new understanding of the complex system. If we do not exactly know a representative for each group, we can estimate them by first applying a rough partitioning algorithm or just an algorithm that aims at finding the hub of very densely connected parts of the graph.

We denote by i 1 , ..., i k the indices of these initial elements.

Background on spectral clustering

One of the most commonly used method to cluster a graph into communities is the spectral clustering method [START_REF] Von | A tutorial on spectral clustering[END_REF]. The algorithm behind spectral clustering has been rediscovered and reapplied in various and different fields, since the initial work of Fiedler [FIE]. For a detailed history of spectral clustering we refer to [START_REF] Daniel | Spectral partitioning works: Planar graphs and finite element meshes[END_REF] and to [START_REF] Von Luxburg | Consistency of spectral clustering[END_REF].

The idea behind spectral clustering is to use eigenvectors of matrices, based on the adjacency matrix, to cluster the graph. In the spectral clustering procedure, ones use the first k eigenvectors of a normalized or unormalized version of the Laplacian matrix (derived from the adjacency one) to cluster the nodes of the graph.

Let G = (V, E) a graph whose adjacency matrix is denoted by A. There are mainly three matrices whose spectral properties can be studied to discover structures in a graph [START_REF] Andrew | Partitioning networks by eigenvectors[END_REF], [START_REF] Von | A tutorial on spectral clustering[END_REF]. These matrices are listed below and essentially depend on the adjacency matrix A.

1. The Laplacian matrix L = D -A.
2. The symmetric Laplacian matrix

L sym = D -1/2 AD -1/2 ,
denoted by L sym because it is a symmetric version of the Laplacian matrix.

3. The random walk Laplacian matrix

L rw = D -1 L = I -D -1 A,
denoted by L rw because D -1 A may represent the transition matrix of a random walk.

The L matrix is often referred as the unormalized Laplacian and L sym , L rw as the normalized Laplacian matrices. To implement spectral clustering one has to compute the first k eigenvectors (those corresponding to the k smallest eigenvalues) of one of the Laplacian matrix above. This step allows to get a representation of the of the initial data into a lowdimensional space in order to be clustered, by k-means for instance. We refer to [START_REF] Von | A tutorial on spectral clustering[END_REF] for details. If these matrices are so important in graph clustering, it is because, as explained in Proposition 4.1 below, the distribution of its eigenvalues indicates the number of connected components in the graphs. In addition, its eigenvectors fully describe the vertices that lie in each of these connected components.

Proposition 4.1. [VL07]

The multiplicity k of the 0 eigenvalue of L and L rw and the multiplicity k of the generalized 0 eigenvalue of L sym are equal to the number of connected components C 1 , ..., C k in the graph.

For L and L rw , the eigenspace associated to 0 is spanned by the indicator vectors

{1 C i } 1≤i≤n .
For L sym , the eigenspace associated 0 is spanned by

D 1/2 1 C i 1≤i≤n .
If the Laplacian (or one of its equivalent) is so appealing, it is because the multiplicity of the null eigenvalue (that corresponds to the smallest eigenvalue) is equal to the number of connected components. In addition, a particular basis of the associated eigenspace is spanned by the community indicators. Therefore, if the graph is made of exactly k connected components, the computation of the eigenvectors of L,L sym and L rw enables to recover these components. When these components are sufficiently connected, they represent communities. In practice, the graph is not made of connected components, but of densely connected subgraphs that are sparsely connected to each other. These densely connected subgraphs represent somehow a perturbed version of the initial connected components that form the communities. If the perturbation is not too high, we can still hope that the eigenvectors of the perturbed Laplacian matrix (associated to this perturbed graph) still contain enough information on the graph structure to detect these communities. In particular, for one specific eigenvectors basis, the vectors coefficients are likely to be very close for indices corresponding to nodes in the same community. Therefore, it is natural to then apply k-means to the rows of the matrix containing these eigenvectors in columns.

The way the eigenvectors basis of the adjacency (or Laplacian matrix) is built is of the highest importance to ensure a good recovery of the communities. To better understand where the idea of this new method comes from, we go back to the ideal case where the different blocks are not connected. In this case, the indicators of the communities {1 C i } 1≤i≤k are the eigenvectors of the normalized and unormalized adjacency or Laplacian matrix. Let U be the concatenation of these vectors. In this situation, we easily see that rows corresponding to indices of nodes in the same class are equal. Hence, clustering the rows of U provides, by the same way, the knowledge of the blocks. Of course, if the adjacency matrix or the Laplacian matrix are perturbed by an additive noise, then the eigenvectors will also be modified. But, if the perturbation is small, we can still hope that the rows (of the modified version of U ) will remain close enough, so that k-means on these rows find the good clusters. However, since 0 is a repeated eigenvalue, the eigenspace associated to 0 is spanned by {1 C i } 1≤i≤k . Hence, there is no guarantee that the implementation of the eigensolvers provides the community indicators as eigenvectors. They can be replaced by a linear combination of the community indicators. For instance, the eigensolvers can find the sum of the indicators as an eigenvector. In this case all the coefficients of the vector are equal to one. Therefore, they are of no use for clustering the nodes of the graph. Once we add a perturbation on the adjacency matrix, the eigenvalues are not multiple anymore and the eigenspace becomes of dimension one. But, the eigenvalues can remain very close and if the eigengap is small the first top eigenvectors given by an eigensolvers may no be very useful to well cluster the groups. The first eigenvectors are not equally informative. This may explain why the original spectral clustering method can fail to recover the good communities in some case. The choice of the k eigenvectors is in fact of the highest importance. The key is to select relevant eigenvectors that provide useful information about the natural grouping of the data. In what follows, we do not use directly the subspace spanned by the first eigenvectors to find the communities but we first compute another eigenbasis that promotes sparse solutions for the eigenvectors.

A new approach

The alternative method we suggest is based on the same principle as spectral clustering. We still focus on the space spanned by the k first eigenvectors. But, instead of computing and directly using one basis among others, we wisely compute from this initial basis (that has been fastly computed by any eigensolver) a basis better suited for clustering.

We do not work on the Laplacian or normalized Laplacian but directly on the adjacency matrix. However, the idea remains the same if we replace the adjacency matrix by the Laplacian or its normalized version by the normalized Laplacian matrix.

The community indicator are the eigenvectors associated to the largest eigenvalues: the eigenvalues of A associated to {1 C i } 1≤i≤k are equal to d 1 , ..., d k and the other eigenvalues are equal to -1. We assume that the eigenvalues of A denoted by λ 1 , ..., λ n are sorted in decreasing order. Let u 1 , .., u n be the associated normalized eigenvectors given by any eigensolvers, so that the k first eigenvectors of A (associated to the k largest eigenvalues) are denoted by u 1 , ..., u k . We denote by U k the matrix that contains u 1 , ...u k in columns and by V k the one that contains u k+1 , ..., u n . We define We recall that v 0 =| {j : v j = 0} |. In other words, 1 C 1 is the sparsest non-zero eigenvector in the space spanned by the first k eigenvectors.

U k = Span {u 1 , ..., u k } .
Proof. Since {1 C i } 1≤i≤k is a basis of U k , a vector v in U k can be written as v = k j=1 α j 1 C j where (α 1 , ..., α k ) ∈ R k \ {0} . Therefore, we deduce that v 0 is equal to 1 α 1 =0 s 1 + ... + 1 α 1 =0 s k .
Because at least one of the α i is non zero and s 1 ≤ s 2 ≤ ... ≤ s k , the vector in U k with the smallest l 0 norm is the one for which α 1 = 0 and α i = 0 for all i = 1.

We can generalized Proposition 4.2 to find the other indicators of the communities.

For i = 2, ..., k, let U i k = {v ∈ U k : v ⊥ 1 C l , l = 1, ..., i -1}. Proposition 4.3. For i = 2, ..., k, the minimization problem argmin v∈U i k \{0}
v 0 has a unique solution (up to a constant) given by 1 C i .

Notice that the constraints are linear. However, because of the l 0 -norm this minimization problem is NP-hard. Fortunately, based on the knowledge of one representative for each group, we can replace the l 0 -norm by its convex relaxation given by the l 1 -norm.

Recall that i 1 , ..., i k are the indices of these representative elements and let

Ũk = {v ∈ U k : v i 1 = 1} .
This is straightforward to see that the community indicator of the smallest community is solution of the following optimization problem.

Proposition 4.4. The minimization problem (P 1 )

argmin v∈ Ũk v 1
has a unique solution given by 1 C 1 .

Proof. Since {1 C i } 1≤i≤k is also a basis of U k , a vector v in U k can be written as v = k j=1 α j 1 C i where (1, ..., α k ) ∈ R k . We deduce that v 1 is equal to α 1 s 1 + ... + α k s k . Because at least one of the α i is not zero and s 1 ≤ s 2 ≤ ... ≤ s k , the vector in U k that satisfies v ∞ = 1 and has the smallest l 1 norm is the one for which α 1 = 0 and α i = 0 for all i = 1 and α 1 = 1.

To simplify and without loss of generality, we assume that i 1 corresponds to the first index (up to a permutation).

Corollary 4.5. Problem (P 1 ) is equivalent to

min ṽ∈R n-1 (1,ṽ)∈U k ṽ 1 .
Because the columns of the matrix U form an orthonormal basis, v ∈ U k is equivalent to V T k v = 0, where we recall thatV k is the restriction of U to the last n -k columns.

Let w be the first column of V T k . We define W as the matrix V T k whose first column w has been deleted. This solution v * is equal to 1 C 1 . There exists very efficient algorithms that solve this type of l 1 -minimization problem with linear constraints. They have been proved to converge to the right solution and can be easily solved using R or Matlab. For instance, we can use the R Optimization Infrastructure (ROI) package or the l 1 -eq function, from the Matlab optimization package l 1 -Magic.

The other community indicators are computed in the same way, adding the constraints that the target vector is orthogonal to the previous computed vectors. In practice, we can deflate the matrix A. We get a matrix Ã, so that the indicator of the second smallest community corresponds now to the sparsest eigenvector associated to the space spanned by the k largest eigenvalues of Ã. Hence, the problem is traced back to the first one and so on.

Minimization problem under perturbations

In practice, we do not have access to this unperturbed graph. So, the question is what if the adjacency is perturbed as in Equation (2) ? We denote by Ûk the perturbed version of U k . This matrix contains the first k eigenvectors of the adjacency matrix  associated to the observed graph Ĝ. Vk denotes the matrix containing the others n -k eigenvectors.

To simplify, we just present the solution to find the first community indicators (for the others, the idea remains the same except that we add the constraint of being orthogonal to the previous solution vectors). The solution consists in releasing the equality constraints of Problem ( P1 ) given in Proposition 4.6. This is equivalent to solve the minimization problem ( P1 )

argmin ṽ∈R n-1 Ŵ ṽ + ŵ 2 2 +λ ṽ 1 , ( P1 )
where λ > 0 is the penalty parameter, Ŵ ∈ M n-k,n-1 is the matrix V T k whose first column ŵ has been deleted. The term Ŵ ṽ + ŵ 2 2 means that we search for a vector close to the space spanned by the first k eigenvectors of  and whose first coefficient is equal to one. ṽ 1 is what controls the sparsity of the solution. As for all regularizing methods depending on a parameter, the main issue is the choice of λ. Figure 1 below shows that the behaviour of the estimated coefficients is of two kinds. The simulations have been performed on a model with nine communities with size between 10 and 30 and a perturbation equal to 0.1. There is a clear splitting in the behaviour of the coefficients, depending if they belong to the first community or not. By looking in more details to the data, we see that the upper batch of curves are associated to nodes in the first community and the lower batch of curves to ones in the other communities. This is true whatever is the value of the penalty parameter. Figure 1 below does not represent a particular situation but a typical behaviour of the Lasso when applied to our model (we have implemented models with various parameters). The graph has five communities, of size between 20 and 50, that have been perturbed with a value of p equal to 0.2. Here again, we retrieve this particular behaviour of the estimated coefficients. Of course this splitting vanished as p increases. This peculiar behaviour can be explained by the fact that the ideal target parameter has coefficients equal to zero or one and does not take continuous values. In addition, the fact that one of the coefficients in the true community is already equal to one forces the other coefficients in the same community to be close to one too, under small perturbations. So that we can hope to discriminate the membership of the nodes by keeping an equality constraint and then hardly thresholding the coefficients with respect to one-half.

Finally, the first community indicators 1 C 1 is estimated as follows.

1. Compute ṽ ∈ argmin

u∈R n-1 Ŵ v=-ŵ v 1 .

Compute v1 = (1, ṽ).

For the other vectors ((v i ) 2≤i≤k ), we add the constraint of being orthogonal to the previous computed vectors and we do the same to estimate the other community indicators. Then, for all i = 1, ..., k, 1 C i is estimated by 1C i where

1C i j := 1 if (v i ) j > 1 2 and (v l ) j = 1, l = 1, ..., i -1 0 if (v i ) j ≤ 1 2 .

Algorithm

We detail below the algorithm we suggest to use to cluster nodes of a graph into k communities. This algorithm can be easily implemented using R or Matlab and is called the l 1 -spectral clustering algorithm. The l 1 -spectral clustering method sequentially build

., k

Step 1: Consider c i the edge representative associated to the i-th community.

Step 2: Compute the eigendecomposition [U, D] of A i.e. A = U D t U .

Step 3: Sort the eigenvalues of A in increasing order and do the same for the associated eigenvectors.

Step 4: Compute the matrix R that contains the eigenvectors associated to the n-k+i+1 smallest eigenvalues

Step 5: Compute V = t R.

Step 6: Compute W = V -c i and w = V c i (where w = V c i is the c th i column of V and V -c i is the V matrix where we have removed the c th i column).

Step 7: Compute the solution s i of the following problem min u∈R n-1 W u=-w u 1 .

(using for instance the l1eq Matlab function).

Step 8: Form the solution

f i = s i 1 s i 2 ...s i c i -1 1 s i c i ...s i n .
Step 9: Compute F = [F f i ] and deflate A with f i . End For.

Step 10: Do

F ij = 1 if Fij ≥ 1/2 and F il = 1, l = 1, ..., i -1 Fij = 0 if F ij < 1/2
OUTPUT k vectors v 1 , ..., v k that are the columns of F (v i j = 1 means that the edge j belongs to community i).

k vectors representing the k community indicators. Algorithm 1 details the main steps of the procedure.

In algorithm 1, we can replace A by D -1 A and the singular value decomposition of A by the computation of the generalized eigenelements of D -1 A.

Remarks:

1. One of the advantage of this algorithm is that it is computationally feasible, even for large graphs, thanks to efficient algorithms that solve l 1 minimization problems.

2. In practice, we may just hope to have at hand a representative for each of the k communities. However, we do not know which one belongs to the smallest community.

If the number of community is not too large, we can still proceed as described above by reviewing the k possible choices and choosing the one for which the objective function is minimal. This requires k! more step but if k is small this is not very time-consuming.

Frobenius norm of the perturbation

To sum up, finding communities in the ideal case turns out to be equivalent to solve

min ṽ∈R n-1 W ṽ=-w ṽ 1 (P)
After perturbation, the community indicators are estimated by solving

min ṽ∈R n-1 Ŵ ṽ=-ŵ ṽ 1 . ( P)
The objective function still remains the same. Only the constraints space has been perturbed. Let E = A -Â be the perturbation applied to the initial adjacency matrix. A natural question is under which conditions on E (and thus on the parameter p of the Bernoulli matrix that represents the noise) can we expect that the solution of Problem ( P) remains closed to the one of Problem (P) and what is the rate of convergence? A noise perturbation on A implies a perturbation on U and thereby on W and w (since all these objects depend on the eigenvalues of U ). If a small level of noise on A leads to a small perturbation of the eigenvectors of the associated normalized adjacency matrix then there is a hope to recover the community structure. So the main issue is what is the stability of the eigenvectors to matrix perturbations? Matrix perturbation theory [START_REF] Stewart | Matrix perturbation theory[END_REF] indicates that it essentially depends on the Frobenius norm of E and on the eigengap. This is the Davis-Kahan theorem stated below.

Theorem 5.1. [SSJ90] Let A, E ∈ M n (R) be symmetric matrices and let . F be the Frobenius norm. Consider à := A + E as a perturbed version of A. Let S 1 ⊂ R. be an interval. Denote by σ S 1 (A) the set of eigenvalues of A which are contained in S 1 , and by V 1 the eigenspace corresponding to all those eigenvalues. Denote by σ S 1 ( Ã) and by Ṽ1 the analogous quantities for Ã. Define the distance between S 1 and the spectrum of A outside of S 1 as

δ = min {| λ -s |; λ eigenvalue of A, λ / ∈ S 1 , s ∈ S 1 } . Then the distance d(V 1 , Ṽ1 ) := sin Θ(V 1 , Ṽ1 ) F between the two subspaces V 1 and Ṽ1 is bounded by d(V 1 , Ṽ1 ) ≤ E δ .
Here after, we assume without loss of generality that each node in the observed graph has a degree larger than one.

Expression of the error term

We recall that A ii = 0 and A ij , i = j is defined by

A ij = A ij + B ij (mod 2) =    1 -B ij if (i, j) ∈ 1≤l≤k J ll - B ij otherwise .
Therefore, the degree matrix of A is given by

D A = diag d A 1 , ..., d A n
where, for all l = 1, ..., k and i ∈ M l ,

d A i = n j=1 A ij = j∈M l j =i (1 -B ij ) + j∈M c l B ij = d l - j∈M l j =i B ij + j∈M c l B ij . Proposition 5.2. Â = A + E where E ∈ M n (R) is
given by

E ij = A ij + B ij (mod 2) =    -B ij if (i, j) ∈ 1≤l≤k J ll - B ij otherwise when i = j and E ii = 0.
Proposition below provides an expression of the difference between D A -1 A and (D A ) -1 A in terms of the elements of A and B.

Proposition 5.3. D Â -1 Â = (D A ) -1 A + E where the entries of E ∈ M n (R) are given by

           E ij =        - 1 d Aε i + d l d Aε i d l + B ij if (i, j) ∈ J ll -, 1 ≤ l ≤ k, i = j B ij d Aε i + d l if (i, j) ∈ J lm , 1 ≤ l = m ≤ k E ii = 0
where

• d l := d A i = n j=1 A ij , i ∈ M l . • d Aε i := d Â-A i = - j∈M l j =i B ij + j∈M c l B ij = d B i -2 j∈M l j =i B ij . • d B i = n j=1 j =i B ij .
Proof. See Subsection 5.3.

Frobenius norm of the error

Proposition 5.6 and Proposition 5.4 below gives the expression of the Frobenius norm of the unormalized and normalized adjacency matrix.

Proposition 5.4. The Frobenius norm of E, that satisfies  = A + E, is equal to

E 2 F = n j=1 j =i B ij = 2 n i=1 j>i B ij .
This proposition is a straightforward consequence of the definition of B and of the fact that B 2 ij = B ij and B ij = B ji . Corollary 5.5.

E E 2 F = n(n -1)p and

E d U k , Ûk ≤ n(n -1)p s 1 ,
where we recall that s 1 is the size of the smallest community.

In particular, if all the communities are of equal size, we get

E d U k , Ûk ≤ (n -1)kp.
If the number of nodes is assumed to be fixed, we easily see that the distance between U k and Ûk will tend to zero as p goes to zero.

Proposition 5.6. The Frobenius norm of E, that satisfies

D A -1 A = (D A ) -1 A + E, is
equal to

E 2 F = k l=1 i∈M l   d B i d Aε i + d l d l   = k l=1 1 d l   i∈M l d B i d l 1 + d Aε i d l -1   ,
where we recall that

• d l := d A i = n j=1 A ij , i ∈ M l . • d Aε i := d Â-A i = - j∈M l j =i B ij + j∈M c l B ij = d B i -2 j∈M l j =i B ij . • d B i = n j=1 j =i B ij .
Another expression of the Frobenius norm only in terms of (B ij ) 1≤i =j≤n is given by

E 2 F = k l=1 1 d l i∈M l n j=1 j =i   B ij j∈M l j =i (1 -B ij ) + j∈M c l B ij   .
Because, it is not possible to exactly compute the expectation of the ratio

d B i d Aε i + d l ,
we just provide an approximation of the expectation. Let R and S be two discrete random variables where S has no mass at 0. Using a Taylor expansion of f : (x, y) → x y , we have

E R S ≈ E (R) E (S) (f irst order) and E R S ≈ ER ES - Cov(R, S) E 2 S + Var(S)ER E 3 S
(second order).

We apply this result with R = d B i and S = d Aε i + d l . Corollary 5.7. In a first order approximation, we have

E E 2 F ≈ k l=1 s l d l (n -1)p d l (1 -2p) + (n -1)p (f irst order)
and

E d U k , Ûk s k -1 s k k l=1 s l d l (n -1)p d l (1 -2p) + (n -1)p (f irst order)
where we recall that s k is the size of the largest community.

In particular, if all the communities are of equal size, we get

E d U k , Ûk pk 2 (n -1) (n -k)(1 -2p) + (n -1)kp (f irst order).
These results provide a first understanding of what theoretical results could be expected for the l 1 -spectral clustering method and how the level of noise p impacts on the eigenspace associated to the community indicators.

Proof

Proof of Proposition 5.3

Proof. We have

D Â -1 Â = (D A + D Aε ) -1 (A + A ε ) ,
where A ε = Â -A and

• A ε := Â -A.
The entries of this matrix are equal to 1 when an edge is added and to -1 when an edge is removed. The other entries are 0. In other words,

(A ε ) ij = A ij -A ij =    -B ij if (i, j) ∈ 1≤l≤k J ll - B ij otherwise . • D Aε := D Â -D A .
This matrix is diagonal and its non zero entries denoted by

d Aε i 1≤i≤n
represent the difference of degree between the observed and the ideal graph, for each of the n vertices. We have, for all l ∈ {1, ..., k} and i ∈ M l ,

d Aε i = - j∈M l j =i B ij + j∈M c l B ij .

Proof of Proposition 5.6

Proof.

E F = n i=1 n j=1 E 2 ij = 1≤l =m≤k (i,j)∈J lm 1 d Aε i + d l 2 (B ij ) 2 + k l=1 (i,j)∈J - ll    1 d Aε i + d l 2 d Aε i d l + B ij 2    . = k l=1 i∈M l 1 d Aε i + d l 2 k m=1 m =l j∈Mm (B ij ) 2 + k l=1 i∈M l 1 d Aε i + d l 2 j∈M l j =i (B ij ) 2 + k l=1 i∈M l j∈M l j =i 1 d Aε i + d l 2 d Aε i d l 2 + k l=1 i∈M l j∈M l j =i 1 d Aε i + d l 2 2 d Aε i d l B ij .
On the one hand,

k l=1 i∈M l 1 d Aε i + d l 2 k m=1 m =l j∈Mm (B ij ) 2 + k l=1 i∈M l 1 d Aε i + d l 2 j∈M l j =i (B ij ) 2 = k l=1 i∈M l 1 d Aε i + d l 2    k m=1 m =l j∈Mm (B ij ) 2 + j∈M l j =i (B ij ) 2    = k l=1 i∈M l 1 d Aε i + d l 2   j∈ k m=1 Mm\{i} (B ij ) 2   = k l=1 i∈M l 1 d Aε i + d l 2    n j=1 j =i (B ij ) 2    .
On the other hand,

k l=1 i∈M l j∈M l j =i 1 d Aε i + d l 2 d Aε i d l 2 = k l=1 i∈M l 1 d Aε i + d l 2 d Aε i 2 d l using that j∈M l j =i 1 = d l and k l=1 j∈M l j =i i∈M l 1 d Aε i + d l 2 2 d Aε i d l B ij = - k l=1 i∈M l 1 d Aε i + d l 2 d Aε i 2 d l + k l=1 i∈M l 1 d Aε i + d l 2 d Aε i d l n j=1 j =i B ij based on the fact that 2 j∈M l j =i B ij = n j=1 j =i B ij -d Aε i .
To conclude

E F = k l=1 i∈M l 1 d Aε i + d l 2    n j=1 j =i (B ij ) 2    + k l=1 i∈M l 1 d Aε i + d l 2 d Aε i 2 d l - k l=1 i∈M l 1 d Aε i + d l 2 d Aε i 2 d l + k l=1 i∈M l 1 d Aε i + d l 2 d Aε i d l n j=1 j =i B ij = k l=1 i∈M l 1 d Aε i + d l 2    n j=1 j =i (B ij ) 2    + k l=1 i∈M l 1 d Aε i + d l 2 d Aε i d l    n j=1 j =i B ij    = k l=1 i∈M l    1 d Aε i + d l 2    n j=1 j =i B ij    1 + d Aε i d l    because B ij ∈ {0, 1} so B 2 ij = B ij and thus n j=1 j =i B 2 ij = n j=1 j =i B ij , = k l=1 i∈M l   d B i d Aε i + d l d l   .
6 Test of the new algorithm on simulated data

In Section 4, we have introduced a new algorithm (called l 1 -spectral clustering) that aims at detecting community structures in complex graphs. This algorithm use spectral vector partitioning techniques to classify nodes. To illustrate the performances of the l 1 -spectral clustering, we simulate random undirected graphs generated from the model presented in Section 3 to then apply the algorithm of Subsection 4.4.

Using Matlab, we first generate random graphs with an exact group structure. We choose different number of blocks and different sizes for the blocks. Then, we add a noise on the associated adjacency matrices. Once the matrix is disturbed, we have no block structure anymore. To recover this underlying block structure, we apply the l 1 -spectral clustering algorithm. We refer to Figure 3 for a summary of these different steps. the histogram of the eigenvectors as given by the Matlab eigensolver (these eigenvectors are the ones used to cluster the data in the traditional spectral clustering method), c) the histogram of the estimated community indicators using l 1 -spectral clustering, d) same thing but applying the traditional spectral clustering method with k-means. In this specific case, the l 1 estimated eigenvectors exactly fit the true ones, whereas k-means makes a few mistakes. Then, we test the robustness to perturbations and the performance of the algorithm. To do so, we consider different values of p. p represents the level of noise that has been discretized between 0 and 0.5. For each fixed value of p, we simulate 100 Monte-Carlo replicates of the random model. We apply the l 1 -spectral clustering algorithm to cluster the nodes. Then, we evaluate the performances of the algorithm by computing the percentage of misassigned nodes in average defined as 1 100 100 j=1 | {i ∈ V : τ (i) = τj (i)} |, where τ j is the block membership function and τj is the estimated membership function for the j-th model. The obtained results have been plotted in Figure 5 and in Figure 6. The results are good and the algorithm seems to work well on simulated data for small perturbations. The rate of exact assignment is equal or very close to one for small perturbations. In addition, thank to the l 1 norm this algorithm is very fast, even for a large number of nodes, when the number of communities is small. These results should be investigated further to better understand the advantages but also the drawbacks induced by this method. It would be of interest to see if it could be possible to set phase transition phenomena for this model, in the same vein as the ones stated by [START_REF] Decelle | Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications[END_REF], [MNS12, MNS13, MNS14], [START_REF] Abbe | Exact recovery in the stochastic block model[END_REF], [START_REF] Abbe | Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms[END_REF] for the stochastic block model when the number of nodes tends to infinity.

Conclusion

We have introduced a random graph model that is closely related to a stochastic block model. The observed graph is assumed to result from a deterministic graph with an exact community structure, whose edges have been perturbed by Bernoulli variables. We have characterized the indicators of the communities in the ideal graph as the ones that have the minimal l 1 -norm with respect to a specific restricted space. We have presented a variant of the spectral clustering algorithm where the vectors used to partitionned the graph are a kind of denoised version. The main advantages of this method is that the objective function is clear, simple and easy to implement even for very large graphs and this procedure seems to work well on simulated data. We have investigated some of the properties of the noise matrix and we have studied the performances of this method on simulated data. However, the main limitation is that it requires the knowledge of one representative for each of the communities.

  4.3.1 Community detection in the ideal caseProposition 4.2 and Proposition 4.3 below show that the community indicators are solution of some specific minimization problem. Proposition 4.2. The minimization problem argmin v∈U k \{0} v 0 has a unique solution (up to a constant) given by 1 C 1 .

Proposition 4. 6 .

 6 The solution v * of problem ( P1 ) is given by v * = (1, ṽ * ) where ṽ * ∈ argmin ṽ∈R n-1 W ṽ=-w ṽ 1 .

Figure 1 :

 1 Figure 1: Lasso path for the first community indicators estimates

Figure 2 :

 2 Figure 2: Illustration of the Lasso path for the four community indicators estimates

Algorithm 1 l 1

 1 -spectral clustering algorithm INPUT Adjacency matrix A of the observed graph G = (E, V ), number of communities k and the community representatives c 1 , ..., c k . F = []. For i = 1, ..

Figure 3 :

 3 Figure 3: Recovery of the block structure

Figure 4 :

 4 Figure 4: Histogram of a) the true community indicators, b) the eigenvectors given by SVD b) the estimated ones by l 1 spectral clustering, c) the estimated ones by k-means

  number of perturbated edges in the graph Rate of exact recovery Impact of perturbation on clustering

Figure 5 :

 5 Figure5: Fraction of nodes correctly classified using l 1 spectral clustering, as the level of noise varies in random generated graphs of the type described above. Size of the groups between 20 and 30. Number of groups between 10 and 20.

Figure 6 :

 6 Figure6: Fraction of nodes correctly classified using l 1 spectral clustering, as the level of noise varies in random generated graphs of the type described above. Size of the groups between 50 and 100. Number of groups between 20 and 30.

To simplify the notations, let F := (D A + D Aε ) -1 and C

F is a diagonal matrix and its entries are equal to

for all l = 1, ..., k and i ∈ M l . Then, computing the inverse of the diagonal matrices D A + D Aε and D A , we deduce that C is also a diagonal matrix whose entries (c i ) 1≤i≤n are equal to

for all l = 1, ..., k and i ∈ M l . Thus, on the one hand,

On the other hand, CA is a block diagonal matrix and its entries are defined by

To conclude, for i = j

and it is straightforward to see that E ii = 0.