Algorithm Compile

This script has been wrote to automate the compilation process. It gather gcc, g++ and fortran for each version of them. It has been thinked as a multiplexer defining the differents branchs of the switch. Each branch correspond to a specific way to act (with options, wit a given name, etc). To understand it, I will explain the differents steps of the algorithm. The first switch is ruled by the mode parameter defining the compilation directives as chain, modular, mpi, openmp and lib associations compilation. Each af these branchs will be splitted into differents sections ruled by a main loop coursing parameters list :

• We read extension and define differents flags used to get the correct path

• For each extension we split again the algorithm using a switch for new falgs as :

-exe_flag : It determine if the exe filename is specified or not -rep_flag : It determines if the repertory name is specified or not • Once the path determined by the differents flags, we automate the compilation process calling the right method, for example :

-gcc $parameters $lib -o $name $lib_option || gcc $lib -L $parameters -o $name || error will give a compilation via variables substitution. The || allow to test the first command, goes to the second if failed and finally call the error method to get a print. The differents used variables in this example are :

This script has been developped to automate the compilation process. It treat c, c++ and fortran source files. Compilation can be ruled with four modes :

• The chain mode realize a chain compilation mode : Each source file is compiled independantly from each other

• The modular mode realize a modular compilation using one main source file and the dependency modules and functions as source files.

• The Mpi compilation mode allow parallel compilation using Open Mpi

• The Openmp compilation mode allow parallel compilation using Open MP

• The Librairies Linking Mode allow modular compilation using Unix Librairies This mode must be specified as argument.

The script take 2 types of arguments : the first one determine the mode between

• 1 (chain)

• 2 (modular)

• 3 (mpi compilation)

• 4 (openmp compilation)

• 5 (Librairies linking mode)

The others parameters are the source files to compile. The source file must be .c, .cpp or fortran files. Others extensions files WILL NOT BE TREATED.

You have to use the correct syntaxe specifying the mode for each execution :

./compile.sh mode source file 1 source file 2 . . . source file n

In case of modular compilation, please to keep this parameter structure :

./compile.sh mode Main source file Module source file 1 Module source file 2 . . .

• -O : In case of additionnal features like Librairies using an option like math.h or compilater directive options as -lpthread, etc. . . It will act as enlarged compilater options directive. Option(s) as following arguments (MUST be specified as the last parameters) : ./compile.sh mode source file 1 source file 2 . . . source file n -O -lm . . . printf" An error occured, please to check the help file using --help option or -˓→h option.

" echo $USER #| mail -s "error" matthieu.cabos@tse-fr.eu

} rep= echo $1 | grep [0-9] if [ "$rep" = "" ] || [ $# -eq 0 ] || [ "$1" = "--help" -o "$1" = "-h" ] || [ $# -lt 2 ]␣ ˓→|| [ $1 -gt 5 ] || [ echo $1 | grep [0-9] = "" ] || [ $1 -le 0 ] then help exit fi rep_flag=0 repertory="" lib="" ind=0 exe_name="" exe_flag=0 param_list="" lib_option="" lib_opt_flag=0 mode=$1 arguments="" exe=0 for i in $@ do if [ "$i" != "1" ] && [ "$i" != "2" ] && [ "$i" != "3" ] && [ "$i" != "4" ] && [
˓→"$i" != "5" ] then arguments=$arguments" "$i fi done for i in $arguments # Treating options flags do # Getting lib parameters ˓→= "f95" ]&& [ "$e" != "F90" ]&& [ "$e" != "F" ] && [ "$e" != "f03" ] && [ "$e" != "F03

(continues on next page) if [ echo $i | grep "\-\d.*" != "" ] 2> /dev/null then (( rep_flag+=1 )) repertory= echo $i | sed -e "s|-d||g" test= echo $repertory | grep "/$" if [ "$test" = "" ] 2> /dev/null then repertory=$repertory"/" fi elif [ "$i" = "-l" ] && [ $ind -eq 0 ] then (( ind+=1 )) elif [ $ind -ne 0 ] then lib="$lib"" ""$i" elif [ "$i" = "-o" ] && [ $exe_flag -eq 0 ] then exe_flag=1 elif [ $exe_flag -ne 0 ] then exe_name=$i ((exe_flag=0)) ((exe=1)) elif [ "$i" = "-O" ] then lib_opt_flag=1 elif [ $lib_opt_flag -ne 0 ] then lib_option=$lib_option" "$i elif [ echo $i | grep "\-\L.*" != "" ] 2> /dev/null then lib_option=$lib_option" "$i elif [ echo $i | grep "\-\I.*" != "" ] 2> /dev/null then lib_option=$lib_option" "$i else param_list=$param_list" "$i fi done if [ $exe -eq 1 ] then ( (
˓→" ] 2> /dev/null then e=${i#*.*.} fi while [ "$e" != "c" ] && [ "$e" != "cpp" ] && [ "$e" != "f90" ] && [ "$e ˓→" != "f95" ]&& [ "$e" != "F90" ]&& [ "$e" != "F" ] && [ "$e" != "f03" ] && [ "$e" !=

$lib -L $relative_way$i -o $relative_way$name || error elif [ $exe_flag -eq 1 ] && [ $rep_flag -eq 1 ] then g++ $relative_way$i $lib -o $relative_way$exe_name $lib_option␣ ˓→|| g++ $lib -L $relative_way$i -o $relative_way$exe_name || error fi else if [ $exe_flag -eq 0 ] && [ $rep_flag -eq 0 ] then g++ $i -o $name $lib_option || error elif [ $exe_flag -eq 1 ] && [ $rep_flag -eq 0 ] then g++ $i -o $exe_name $lib_option || error elif [ $exe_flag -eq 0 ] && [ $rep_flag -eq 1 ] then g++ $relative_way$i -o $relative_way$name $lib_option || error elif [ $exe_flag -eq 1 ] && [ $rep_flag -eq 1 ] then g++ $relative_way$i -o $relative_way$exe_name $lib_option ||␣ ˓→error fi (continues on next page) 8
Chapter 1. Compile fi # Compiling the code file as parameter elif [ "$e" = "f90" -o "$e" = "f95" -o "$e" = "F90" -o "$e" = "F" -o "$e ˓→" = "f03" -o "$e" = "F03" ] then e=".""$e" name= basename $i $e # Getting the .exe filename

if [ $exe_flag -eq 0 ] && [ $rep_flag -eq 0 ] then gfortran -o $name $i $lib_option || error elif [ $exe_flag -eq 1 ] && [ $rep_flag -eq 0 ] then gfortran -o $exe_name $i $lib_option || error elif [ $exe_flag -eq 0 ] && [ $rep_flag -eq 1 ] then gfortran -o $relative_way$name $relative_way$i $lib_option ||␣ ˓→error elif [ $exe_flag -eq 1 ] && [ $rep_flag -eq 1 ] then gfortran -o $relative_way$exe_name $relative_way$i $lib_option␣ ˓→|| error fi # fi fi done elif [ $mode -eq 2 ] # Executing script profile in Modular Compilation mode then for i in $param_list do if [ "$i" != "1" ] # Rebuilding the file name parameters list then if [ $rep_flag -eq 0 ] then parameters=$parameters" "$i elif [ $rep_flag -eq 1 ] then parameters=$parameters" "$relative_way$i fi fi done for i in $parameters # Brownsing parameters list do e=${i#*.} # Getting the file extension testeur_beg="{i#*." testeur_end="*.} " ((counter=1)) if [ "$e" != "c" ] && [ "$e" != "cpp" ] && [ "$e" != "f90" ] && [ "$e" ! ˓→= "f95" ]&& [ "$e" != "F90" ]&& [ "$e" != "F" ] && [ "$e" != "f03" ] && [ "$e" != "F03 ˓→" ] 2> /dev/null (continues on next page) 1.4. Source Compile then e=${i#*.*.} fi while [ "$e" != "c" ] && [ "$e" != "cpp" ] && [ "$e" != "f90" ] && [ "$e ˓→" != "f95" ]&& [ "$e" != "F90" ]&& [ "$e" != "F" ] && [ "$e" != "f03" ] && [ "$e" != ˓→"F03" ] 2> /dev/null # then do e=${i#*..*.} done if [ "$e" = "c" ] then name= basename $i '.c' # Getting the .exe filename break elif [ "$e" = "cpp" ] then name= basename $i '.cpp' # Getting the .exe filename break fi done if [ "$e" = "c" ] then if [[ ! $lib = "" ]] then if [ $exe_flag -eq 0 ] && [ $rep_flag -eq 0 ] then gcc $parameters $lib -o $name $lib_option || gcc $lib -L ˓→$parameters -o $name || error elif [ $exe_flag -eq 1 ] && [ $rep_flag -eq 0 ] then gcc $parameters $lib -o $exe_name $lib_option || gcc ˓→$lib -L $parameters -o $exe_name || error elif [ $exe_flag -eq 0 ] && [ $rep_flag -eq 1 ] then gcc $parameters $lib -o $relative_way$name $lib_option␣ ˓→|| gcc $lib -L $parameters -o $name || error elif [ $exe_flag -eq 1 ] && [ $rep_flag -eq 1 ] then gcc $parameters $lib -o $relative_way$exe_name ˓→$lib_option || gcc $lib -L $parameters -o $relative_way$exe_name || error fi else if [ $exe_flag -eq 0 ] && [ $rep_flag -eq 0 ] then gcc $parameters -o $name $lib_option || error elif [ $exe_flag -eq 1 ] && [ $rep_flag -eq 0 ] then gcc $parameters -o $exe_name $lib_option || error elif [ $exe_flag -eq 0 ] && [ $rep_flag -
[ "$e" = "cpp" ] then if [[ ! $lib = "" ]] then if [ $exe_flag -eq 0 ] && [ $rep_flag -eq 0 ] then g++ $parameters $lib -o $name $lib_option || g++ $lib -L ˓→$parameters -o $name || error elif [ $exe_flag -eq 1 ] && [ $rep_flag -eq 0 ] then g++ $parameters $lib -o $exe_name $lib_option || g++ ˓→$lib -L $parameters -o $exe_name || error elif [ $exe_flag -eq 0 ] && [ $rep_flag -eq 1 ] then g++ $parameters $lib -o $relative_way$name $lib_option␣ ˓→|| g++ $lib -L $parameters -o $name || error elif [ $exe_flag -eq 1 ] && [ $rep_flag -eq 1 ] then g++ $parameters $lib -o $relative_way$exe_name ˓→$lib_option || g++ $lib -L $parameters -o $relative_way$exe_name || error fi else
if [ $exe_flag -eq 0 ] && [ $rep_flag -eq 0 ] then echo "commande écrite : " echo "g++ $parameters -o $name $lib_option" || error echo "resultats obtenus : " g++ $parameters -o $name $lib_option elif [ $exe_flag -eq 1 ] && [ $rep_flag -eq 0 ] then echo "commande écrite : " echo "g++ $parameters -o $exe_name $lib_option" || error echo "resultats obtenus : " g++ $parameters -o $exe_name $lib_option elif [ $exe_flag -eq 0 ] && [ $rep_flag -eq 1 ] then echo "commande écrite : " echo "g++ $parameters -o $relative_way$name $lib_option ˓→" || error echo "resultats obtenus : " g++ $parameters -o $relative_way$name $lib_option elif [ $exe_flag -eq 1 ] && [ $rep_flag -eq 1 ] then (continues on next page)

Source Compile

echo "commande écrite : " echo "g++ $parameters -o $relative_way$exe_name $lib_ ˓→option" || error echo "resultats obtenus : " g++ $parameters -o $relative_way$exe_name $lib_option fi fi # Compiling the Modular file as parameters elif [ "$e" = "f90" -o "$e" = "f95" -o "$e" = "F90" -o "$e" = "F" -o "$e" = "f03

16

Chapter 1. Compile elif [ "$e" = "f90" -o "$e" = "f95" -o "$e" = "F90" -o "$e" = "F" -o "$e" = "f03

˓→" -o "$e" = "F03" ] then for i in $parameters do e=${i#*.} if [ "$e" != "f90" ] && [ "$e" != "f95" ] && [ "$e" != "F90" ] && ˓→ [ "$e" != "F" ] && [ "$e" != "f03" ] && [ "$e" != "F03" ] then e=${i#*.*.} fi e=".""$e" name= basename $i $e if [ $exe_flag -eq 0 ] && [ $rep_flag -eq 0 ] then gfortran -o $name $i $lib_option -fopenmp || error elif [ $exe_flag -eq 1 ] && [ $rep_flag -eq 0 ] then gfortran -o $exe_name $i $lib_option -fopenmp || error elif [ $exe_flag -eq 0 ] && [ $rep_flag -eq 1 ] then gfortran -o $relative_way$name $i $lib_option -fopenmp␣ ˓→|| error elif [ $exe_flag -eq 1 ] && [ $rep_flag -eq 1 ] then gfortran -o $relative_way$exe_name $i $lib_option -˓→fopenmp || error fi done fi elif [ $mode -eq 5 ] #Executing script with librairies Linking mode then libs="" libflag="t" cflag="t" for i in $param_list do if [ "$i" != "4" ] # Rebuilding the file name parameters list then parameters=$parameters" "$i fi done for i in $parameters do e=${i#*.} # Getting the file extension if [ $e != "c" ] && [ $e != "cpp" ] && [ "$e" != "f90" ] && [ "$e" != ˓→"f95" ] && [ "$e" != "F90" ] && [ "$e" != "F" ] && [ "$e" != "f03" ] && [ "$e" != "F03 ˓→" ] then (continues on next page)

Source Compile

e=${i#*.*.} fi if [ $e = "c" ] then name= basename $i '.c' # Getting the .exe filename cflag=$e elif [ "$e" = "cpp" ] then name= basename $i '.cpp' # Getting the .exe filename cflag=$e elif [ "$e" = "o" -o "$e" = "a" -o "$e" = "so" ] then libs="$libs"" ""$i" libflag=$e fi done if In a first step we get essentials informations since command parameters such as Resolution, size, etc. The mode is determine by the keyword 'clean', if not specified the algorithm resize all the pictures found in the folder and associated sub-tree, else it will remove all the resized pictures.

[ $cflag = "c" ] then cflag=".""$cflag" tocompile=$name$cflag if [ "$libflag" = "o" ] # Script profile in case of Object Librairie then if [ $exe_flag -eq 0 ] && [ $rep_flag -
To treat them, we get in the liste variable the list of sub-folders paths.

We brownse each folders in a loop and convert each picture file to the specified size and resolution.

Chapter 2. Converter

Please to use this script with the correct parameters :

./ResConverter.sh Resolution_DPI Folder size to convert all pictures with the specified DPI and size from given folder a root.

or ./ResConverter.sh clean to clean the workspace Where :

• Resolution is a value between 72 and 500 DPI

• Folder is the name of the folder containing pictures

• size is the picture length in pixel. Must have form "800x600".

This script act recursively and will resize all the pictures contained into sub-tree

) fi if [ "$i" = "#include" ] then ((lib_flag=1)) else ((lib_flag=0)) fi done for libp in $lib do ind=0 for i in $(seq 1 ${#libp}) do lettre=$(echo $libp | cut -c$i) if [ ! $ind -eq 0 ] then name_lib="$name_lib""$lettre" fi ((ind=$ind+1)) done name_lib= basename $name_lib '.h>' # name_lib="$name_lib"" " name_lib_final="$name_lib_final"" ""$name_lib" name_lib="" done for i in $name_lib_final do test="" test= vcpkg search $i | grep "[0-9]" if [ "$test" = "" ] then echo "################################################################### ˓→########################" (lib_flag=0)
echo "The librairy ""$i"" is not disponible on the Unix Server, please␣ ˓→to install it manually."

(continues on next page) 30 Chapter 3. Get_lib_list echo "################################################################### ˓→########################"
else install_name="$install_name"" ""$i" fi done for i in $install_name do vcpkg install $i done 3.3. Source Get_lib_list Chapter 3. Get_lib_list CHAPTER FOUR TRANSFERT_SSH.SH

Algorithm Transfert

This script has been thinked to manage ssh Files transfert from the existing ip & User id. In fact, the command scp will be used from differents switches branchs :

• File upload : Permit to upload a file to the specified ssh platform

• File download : Permit to download a file to the specified ssh platform

• Folder upload : Permit to upload a folder to the specified ssh platform

• Folder download : Permit to download a folder to the specified ssh platform These branchs are ruled by the parameter mode.

In the first step, we get variables informations since parameters values. Once done, we update from infos, the differents flags and the defaults paths. These updated fields will be used in the last part of the algorithm :

• Updating the path • Using the scp command with the correct arguments to automate tranfert.

34

Chapter 4. Transfert_ssh.sh

Options Transfert

-help : Get the linux-like help from the command prompt.

38

Chapter 4. Transfert_ssh.sh elif [ $mode -eq 3 ] then if [ echo $dest_way | grep "home/" != "" ] 2> /dev/null then dest_way= echo $dest_way | sed -e "s|/home/$USER|/users/$user|g" fi scp -r $source_way$files $user@$IP:$dest_way elif [ $mode -eq 4 ] then if [ echo $source_way | grep "home/" != "" ] 2> /dev/null then source_way= echo $source_way | sed -e "s|/home/$USER/|/users/$user/|g" fi scp -r $user@$IP:$source_way$files $dest_way fi

  ˓→" -o "$e" = "F03" ] then rename_flag=0 for i in $parameters do e=${i#*.} if [ $e != "c" ] && [ $e != "cpp" ] && [ "$e" != "f90" ]&& [ "$e" != ˓→"f95" ]&& [ "$e" != "F90" ] && [ "$e" != "F" ] && [ "$e" != "f03" ] && [ "$e" != "F03"␣ ˓→] then e=${i#*.*.} fi e=".""$e" name= basename $i $e files=$files" "$i done if [ $exe_flag -eq 0 ] && [ $rep_flag -eq 0 ] then gfortran -o $name $files $lib_option || error elif [ $exe_flag -eq 0 ] && [ $rep_flag -eq 1 ] then gfortran -o $relative_way$name $files $lib_option || error elif [ $exe_flag -eq 1 ] && [ $rep_flag -eq 0 ] then gfortran -o $exe_name $files $lib_option || error elif [ $exe_flag -eq 1 ] && [ $rep_flag -eq 1 ] then gfortran -o $relative_way$exe_name $files $lib_option || error fi if [ $rename_flag -eq 1 ] then rm -r tmp fi fi elif [ $mode -eq 3 ] # Executing script profile in MPI parallel Compilation mode then for i in $param_list do if [ "$i" != "2" ] then parameters=$parameters" "$i fi (continues on next page)12Chapter 1. Compile done for i in $parameters do e=${i#*.} if [ "$e" != "c" ] && [ "$e" != "cpp" ] && [ "$e" != "f90" ] &&␣ ˓→[ "$e" != "f95" ]&& [ "$e" != "F90" ]&& [ "$e" != "F" ] && [ "$e" != "f03" ] && [ "$e"␣ ˓→!= "F03" ] 2> /dev/null then e=${i#*.*.} fi ␣ ˓→ # Getting the file extension while [ "$e" != "c" ] && [ "$e" != "cpp" ] && [ "$e" != "f90" ]␣ ˓→&& [ "$e" != "f95" ]&& [ "$e" != "F90" ]&& [ "$e" != "F" ] && [ "$e" != "f03" ] && [ " ˓→$e" != "F03" ] 2> /dev/null # thendo e=${i#*..*.} done if [ $e = "c" ] then name= basename $i '.c' if [ $exe_flag -eq 0 ] && [ $rep_flag -eq 0 ] then # Getting the .exe filename mpicc -o $name $i $lib_option || error elif [ $exe_flag -eq 1 ] && [ $rep_flag -eq 0 ] then mpicc -o $exe_name $i $lib_option || error elif [ $exe_flag -eq 0 ] && [ $rep_flag -eq 1 ] then mpicc -o $relative_way$name $relative_way$i $lib_option␣ ˓→|| error elif [ $exe_flag -eq 1 ] && [ $rep_flag -eq 1 ] then mpicc -o $relative_way$exe_name $relative_way$i $lib_ ˓→option || error fi # Compiling the code file as parameter elif [ "$e" = "cpp" ] then name= basename $i '.cpp' if [ $exe_flag -eq 0 ] && [ $rep_flag -eq 0 ] then # Getting the .exe filename mpicxx -o $name $i $lib_option || error elif [ $exe_flag -eq 1 ] && [ $rep_flag -eq 0 ] then mpicxx -o $exe_name $i $lib_option || error elif [ $exe_flag -eq 0 ] && [ $rep_flag -eq 1 ] then mpicxx -o $relative_way$name $relative_way$i $lib_option␣ ˓→|| error (continues on next page) 1.4. Source Compile elif [ $exe_flag -eq 1 ] && [ $rep_flag -eq 1 ] thenmpicxx -o $relative_way$exe_name $relative_way$i $lib_ ˓→option || error fi # Compiling the code file as parameter elif [ "$e" = "f90" -o "$e" = "f95" -o "$e" = "F90" -o "$e" = "F ˓→" -o "$e" = "f03" -o "$e" = "F03" ] then e=".""$e" name= basename $i $e # Getting the .exe filenameif [ $exe_flag -eq 0 ] && [ $rep_flag -eq 0 ] then mpifort -o $name $i $lib_option || error elif [ $exe_flag -eq 1 ] && [ $rep_flag -eq 0 ] then mpifort -o $exe_name $i $lib_option || error elif [ $exe_flag -eq 0 ] && [ $rep_flag -eq 1 ] then mpifort -o $relative_way$name $relative_way$i ˓→$lib_option || error elif [ $exe_flag -eq 1 ] && [ $rep_flag -eq 1 ] then mpifort -o $relative_way$exe_name $relative_way ˓→$i $lib_option || error fi # fi fi done elif [ $mode -eq 4 ] # Executing script profile in OpenMP parallel Compilation mode then for i in $param_list do if [ "$i" != "3" ] # Rebuilding the file name parameters list then if [ $rep_flag -eq 0 ] then parameters=$parameters" "$i elif [ $rep_flag -eq 1 ] then parameters=$parameters" "$relative_way$i fi fi done for i in $parameters do e=${i#*.} if [ "$e" != "c" ] && [ "$e" != "cpp" ] && [ "$e" != "f90" ] && [ "$e" ! ˓→= "f95" ]&& [ "$e" != "F90" ]&& [ "$e" != "F" ] && [ "$e" != "f03" ] && [ "$e" != "F03 ˓→" ] 2> /dev/null (continues on next page) 14 Chapter 1. Compile then e=${i#*.*.} fi # Getting the file extension while [ "$e" != "c" ] && [ "$e" != "cpp" ] && [ "$e" != "f90" ] && [ "$e ˓→" != "f95" ]&& [ "$e" != "F90" ]&& [ "$e" != "F" ] && [ "$e" != "f03" ] && [ "$e" != ˓→"F03" ] 2> /dev/null # then do e=${i#*..*.} done if [ $e = "c" ] then name= basename $i '.c' # Getting the .exe filename break elif [ "$e" = "cpp" ] then name= basename $i '.cpp' # Getting the .exe filename break fi done if [ $e = "c" ] then if [[ ! $lib = "" ]] then if [ $exe_flag -eq 0 ] && [ $rep_flag -eq 0 ] then gcc $parameters $lib -o $name -fopenmp $lib_option ||␣ ˓→gcc $lib -L $parameters -o $name -fopenmp || error elif [ $exe_flag -eq 1 ] && [ $rep_flag -eq 0 ] then gcc $parameters $lib -o $exe_name -fopenmp $lib_option␣ ˓→|| gcc $lib -L $parameters -o $exe_name -fopenmp || error elif [ $exe_flag -eq 0 ] && [ $rep_flag -eq 1 ] then gcc $parameters $lib -o $relative_way$name -fopenmp $lib_ ˓→option || gcc $lib -L $parameters -o $relative_way$name -fopenmp || error elif [ $exe_flag -eq 1 ] && [ $rep_flag -eq 1 ] then gcc $parameters $lib -o $relative_way$exe_name -fopenmp ˓→$lib_option || gcc $lib -L $parameters -o $relative_way$exe_name -fopenmp || error fi else if [ $exe_flag -eq 0 ] && [ $rep_flag -eq 0 ] then gcc $parameters -o $name -fopenmp $lib_option || error elif [ $exe_flag -eq 1 ] && [ $rep_flag -eq 0 ] then gcc $parameters -o $exe_name -fopenmp $lib_option ||␣ ˓→error (continues on next page) 1.4. Source Compile elif [ $exe_flag -eq 0 ] && [ $rep_flag -eq 1 ] then gcc $parameters -o $relative_way$name -fopenmp $lib_ ˓→option || error elif [ $exe_flag -eq 1 ] && [ $rep_flag -eq 1 ] then gcc $parameters -o $relative_way$exe_name -fopenmp $lib_ ˓→option || error fi fi # Compiling the Modular file as parameters elif [ $e = "cpp" ] then if [[ ! $lib = "" ]] then if [ $exe_flag -eq 0 ] && [ $rep_flag -eq 0 ] then g++ $parameters $lib -o $name -fopenmp $lib_option ||␣ ˓→g++ $lib -L $parameters -o $name -fopenmp || error elif [ $exe_flag -eq 1 ] && [ $rep_flag -eq 0 ] then g++ $parameters $lib -o $exe_name -fopenmp $lib_option␣ ˓→|| g++ $lib -L $parameters -o $exe_name -fopenmp || error elif [ $exe_flag -eq 0 ] && [ $rep_flag -eq 1 ] then g++ $parameters $lib -o $relative_way$name -fopenmp $lib_ ˓→option || g++ $lib -L $parameters -o $relative_way$name -fopenmp || error elif [ $exe_flag -eq 1 ] && [ $rep_flag -eq 1 ] then g++ $parameters $lib -o $relative_way$exe_name -fopenmp ˓→$lib_option || g++ $lib -L $parameters -o $relative_way$exe_name -fopenmp || error fi else if [ $exe_flag -eq 0 ] && [ $rep_flag -eq 0 ] then g++ $parameters -o $name -fopenmp $lib_option ␣ ˓→|| error elif [ $exe_flag -eq 1 ] && [ $rep_flag -eq 0 ] then g++ $parameters -o $exe_name -fopenmp $lib_ ˓→option || error elif [ $exe_flag -eq 0 ] && [ $rep_flag -eq 1 ] then g++ $parameters -o $relative_way$name -fopenmp ˓→$lib_option || error elif [ $exe_flag -eq 1 ] && [ $rep_flag -eq 1 ] then g++ $parameters -o $relative_way$exe_name -˓→fopenmp $lib_option || error fi fi # Compiling the Modular file as parameters (continues on next page)

  eq 0 ] then gcc -o $tocompile $libs $lib_option || error elif [ $exe_flag -eq 1 ] && [ $rep_flag -eq 0 ] then gcc $tocompile $libs -o $exe_name $lib_option || error elif [ $exe_flag -eq 0 ] && [ $rep_flag -eq 1 ] then gcc $relative_way$tocompile $libs $lib_option ␣ ˓→|| error elif [ $exe_flag -eq 1 ] && [ $rep_flag -eq 1 ] then gcc $relative_way$tocompile $libs -o $relative_way$exe_ ˓→name $lib_option || error fi # Compiling the Modular Libs as parameters elif [ "$libflag" = "a" ] # Script profile in case of Static Librairie then if [ $exe_flag -eq 0 ] && [ $rep_flag -eq 0 ] then gcc $tocompile $libs $lib_option || error elif [ $exe_flag -eq 1 ] && [ $rep_flag -eq 0 ] then gcc $tocompile $libs -o $exe_name $lib_option || error elif [ $exe_flag -eq 0 ] && [ $rep_flag -eq 1 ] then (continues on next page) 18 Chapter 1. Compile gcc $relative_way$tocompile $libs $lib_ ˓→option || error elif [ $exe_flag -eq 1 ] && [ $rep_flag -eq 1 ] then gcc $relative_way$tocompile $libs -o $relative_ ˓→way$exe_name $lib_option || error fi elif [ "$libflag" = "so" ] # Script profile in case of Dynamic Librairie then if [ $exe_flag -eq 0 ] && [ $rep_flag -eq 0 ] then gcc -$libs -L $tocompile $lib_option || error elif [ $exe_flag -eq 1 ] && [ $rep_flag -eq 0 ] then gcc -$libs -L $tocompile -o $exe_name $lib_option ||␣ ˓→error elif [ $exe_flag -eq 0 ] && [ $rep_flag -eq 1 ] then gcc -$libs -L $relative_way$tocompile ˓→$lib_option || error elif [ $exe_flag -eq 1 ] && [ $rep_flag -eq 1 ] then gcc -$libs -L $relative_way$tocompile -o ˓→$relative_way$exe_name $lib_option || error fi fi elif [ $cflag = "cpp" ] then cflag=".""$cflag" tocompile=$name$cflag if [ "$libflag" = "o" ] # Script profile in case of Object Librairie then if [ $exe_flag -eq 0 ] && [ $rep_flag -eq 0 ] then g++ $tocompile $libs $lib_option || error elif [ $exe_flag -eq 1 ] && [ $rep_flag -eq 0 ] then g++ $tocompile $libs -o $exe_name $lib_option || error elif [ $exe_flag -eq 0 ] && [ $rep_flag -eq 1 ] then g++ $relative_way$tocompile $libs $lib_ ˓→option || error elif [ $exe_flag -eq 1 ] && [ $rep_flag -eq 1 ] then g++ $relative_way$tocompile $libs -o $relative_ ˓→way$exe_name $lib_option || error fi # Compiling the Modular Libs as parameters elif [ "$libflag" = "a" ] # Script profile in case of Static Librairie (continues on next page) then if [ $exe_flag -eq 0 ] && [ $rep_flag -eq 0 ] then g++ $tocompile $libs $lib_option || error elif [ $exe_flag -eq 1 ] && [ $rep_flag -eq 0 ] then g++ $tocompile $libs -o $exe_name $lib_option || error elif [ $exe_flag -eq 0 ] && [ $rep_flag -eq 1 ] then g++ $relative_way$tocompile $libs $lib_ ˓→option || error elif [ $exe_flag -eq 1 ] && [ $rep_flag -eq 1 ] then g++ $relative_way$tocompile $libs -o $relative_ ˓→way$exe_name $lib_option || error fi elif [ "$libflag" = "so" ] #Script profile in case of Dynamic Librairie then if [ $exe_flag -eq 0 ] && [ $rep_flag -eq 0 ] then libs="-""$libs" g++ $tocompile $libs $lib_option || error elif [ $exe_flag -eq 1 ] && [ $rep_flag -eq 0 ] then g++ $tocompile $libs -o $exe_name $lib_option || error elif [ $exe_flag -eq 0 ] && [ $rep_flag -eq 1 ] then g++ $relative_way$tocompile $libs $lib_ ˓→option || error elif [ $exe_flag -eq 1 ] && [ $rep_flag -eq 1 ] then g++ $relative_way$tocompile $libs -o $relative_ ˓→way$exe_name $lib_option || error fi been wrote to treat large amount of picture data. It must be use as a resizer. It is ruled by parameters : • Resolution : Define the DPI resolution of the picture • Folder : Determine the root folder to treat • size : Determine the Picture size, must have form axb where a & b are integers (ex : 800x600)

  In case of additional libs, you may define the path of access lib files using the syntax -L./path_to_lib :

	1.4 Source Compile
	#!/bin/bash
	# Author : CABOS Matthieu
	# Date : 28/09/2020
	function help(){
	printf "Please to refer Documentation."
	}
	function error(){
	./compile.sh mode src_file -L/path_to_lib/
	4	Chapter 1. Compile

• -o : If specified you should give the executable the name you want as following argument : ./compile.sh mode src_file -o executable name

• -d : If the source file(s) are not in the current directory, the -d option should specified the directory to treat (-d /my_project_to_compile_directory/ as example) ./compile.sh mode src_file -d src_file_repertory_relative_path

• -I : In case of additional libs, you may define the path of access header files using the syntax -I./path_to_include/ : ./compile.sh mode src_file -I /path_to_include/

• -L :

2.2. Script usage Converter 2.4 Source Converter

	#!/bin/bash # Author : CABOS Matthieu # Date : 23/09/2021 function usage(){ echo " Please to refer Documentation. " } if [ $# -eq 0 ] then usage exit fi ind=1 param=$* mode=0 size=0 for i in $param do if [ $ind -eq 1 ] then if [ "$(echo $i | grep "^[ [:digit:] ]*$")" ] then Resolution=$i elif [ $i == "clean" ] then mode=1 break fi elif [ $ind -eq 3 ] then size=$i fi ind=$((ind+1)) done path="./" Folders= find $2 -type d for f in $Folders do liste= ls $f if [ $mode -eq 0 ] then for item in $liste echo $f"/"$item if [ -f $f"/"$item ] then convert $f"/"$item -resize $size -density $Resolution $f (continues on next page) ˓→"/resized"$item 26 Chapter 2. Converter CHAPTER THREE GET_LIB_LIST #!/bin/bash # Author : CABOS Matthieu # Date : 31/08/2020 lib_flag=0 lib="" for i in $@ # Coursing arguments list do if [ $lib_flag -eq 1 ] # Getting lib name if founded then lib="$lib"" ""$i" 2.4. Source Converter do (

  dest_way | sed -e "s|/home/$USER|/users/$user|g" fi scp $source_way$files $user@$IP:$dest_way elif [ $mode -eq 2 ] then if [ echo $source_way | grep "home/" != "" ] 2> /dev/null then source_way= echo $source_way | sed -e "s|/home/$USER/|/users/$user/|g" fi scp $user@$IP:$source_way$files $dest_way

	4.4 Source Transfert
	Chapter 4. Transfert_ssh.sh (continues on next page) != "" ] 2> /dev/null if [ $# -eq 0 ] || [ $# -ne 6 ] || [ $1 -gt 4 ] || [ $1 -le 0 ] #!/bin/bash # Author : CABOS Matthieu # Date : 23/07/2020 function usage(){ echo"Please to refer Documentation." } param=$* ind=1 files="" index=0 home_flag_src=0 home_flag_dst=0 IP=0 then usage exit fi if [ "$1" = "--help" ] then usage exit fi for i in $param do if [ $ind -eq 1 ] then mode=$i elif [ $ind -eq 2 ] then user=$i elif [ $ind -eq 3 ] then if [ $i = ~] then home_flag_src=1 fi source=$i elif [ $ind -eq 4 ] then if [ $i = ~] then home_flag_dst=1 fi dest=$i elif [ $ind -eq 5 ] files="$i" else IP="$i" fi ind=$((ind+1)) done source_way=$source dest_way=$dest # Xchange source and dest when Mode if [ $mode -eq 1 -o $mode -eq 3 ] then if [ $home_flag_src -eq 1 ] then source_way="/home/$USER" fi if [ $home_flag_dst -eq 1 ] then dest_way="/users/$user" fi else if [ $home_flag_src -eq 1 ] then source_way="/users/$user" fi if [ $home_flag_dst -eq 1 ] then dest_way="/home/$USER" fi fi source_way=$source_way"/" dest_way=$dest_way"/" if [ $mode -eq 1 ] then if [ echo $dest_way | grep "home/" then 4.4. Source Transfert then dest_way= echo $

(continues on next page)

1.2. Script usage Compile

1.4. Source Compile

Chapter 3. Get_lib_list

4.4. Source Transfert

Chapter 5. Sudo-upgrade-all

Algorithm get_lib_list

This algorithm has been wrote to manage Librairies missing notifications when compiling with gcc.

In a first step, I'm coursing arguments list (wich is the results of a failes compilation). In case of Librairie name founded, I update the lib variable and the Lib Flag to True. In a second step, for each founded librairies, I get the exact name of the librairy via the basename command. On the final loop, I try, for each librairy (from the exact name) to install it via the vcpkg command, if founded on server, It will install it, else it will give you the missing Librairies name. Chapter 4. Transfert_ssh.sh CHAPTER FIVE SUDO-UPGRADE-ALL

is the source(s) file(s) to compile * lib : is the specified Librairie to link

Script Get_lib_list

Script Usage.

Please to use this script with the correct arguments. This script analyse the results of a failed compilation and determine the name(s) of the missing librairie(s).

Please to launch using the following syntax :

./get_lib_list.sh gcc my_source_file.c

Script Get_lib_list

Please to use the script with the correct number of arguments :

./transfert.sh mode user source_folder destination_folder filename/foldername IP Where :

• mode is the way to transfert between :

-1 mean upload file to the ssh specified destination folder -2 mean download file since the ssh specified source folder

Script Usage Sudo-upgrade-all

Called without arguments like that : ./sudo-upgrade-all.sh This script is used to upgrade all the present binaries librairies on a Unix system. Please to use if and only if the Unnix system use the apt command (see also sudo apt command in Linux Manual).

Script Usage


Securing the airway in critical care scenarios-questioning the fundamentals Author's reply

Samir Jaber, Audrey de Jong

To cite this version:

Samir Jaber, Audrey de Jong. Securing the airway in critical care scenarios-questioning the fundamentals Author's reply. Intensive Care Medicine, In press, 10.1007/s00134-021-06552-6. hal-03412469


Solenne Gaucher
email: solenne.gaucher@math.u-psud.fr

Olga Klopp
email: kloppolga@math.cnrs.fr

Optimality of variational inference for stochastic block model with missing links

Variational methods are extremely popular in the analysis of network data. Statistical guarantees obtained for these methods typically provide asymptotic normality for the problem of estimation of global model parameters under the stochastic block model. In the present work, we consider the case of networks with missing links that is important in application and show that the variational approximation to the maximum likelihood estimator converges at the minimax rate. This provides the first minimax optimal and tractable estimator for the problem of parameter estimation for the stochastic block model with missing links. We complement our results with numerical studies of simulated and real networks, which confirm the advantages of this estimator over current methods.

Introduction

The analysis of network data poses both computational and theoretical challenges. Most results obtained in the literature concentrate on the stochastic block model (SBM) which is known to be a good proxy for more general models, such as the inhomogeneous random graph model, [START_REF] Lovász | Large Networks and Graph Limits[END_REF]. Recently, variational methods ( [START_REF] Michael | An introduction to variational methods for graphical models[END_REF][START_REF] Wainwright | Graphical Models, Exponential Families, and Variational Inference[END_REF]) have attracted considerable attention as they offer computationally tractable algorithms often combined with theoretical guarantees. Theoretical results that one can find for such variational methods provide asymptotic normality rates for parameter estimates of stochastic block data. For example, consistency has been shown for profile likelihood maximization [START_REF] Bickel | A nonparametric view of network models and newman-girvan and other modularities[END_REF] and variational approximation to the maximum likelihood estimator [START_REF] Daudin | A mixture model for random graph[END_REF], [START_REF] Bickel | Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels[END_REF]. These results have been extended to the case of dynamic stochastic block model [START_REF] Longepierre | Consistency of the maximum likelihood and variational estimators in a dynamic stochastic block model[END_REF] and sampled data [START_REF] Tabouy | Variational inference for stochastic block models from sampled data[END_REF]. These work focus on parameter estimation, as in [START_REF] Pati | On statistical optimality of variational bayes[END_REF] and [START_REF] Yang | α-variational inference with statistical guarantees[END_REF], who establish the minimax optimality of variational methods in a large class of models (which does however not include the stochastic block model). Variational inference has also been successfully applied to the problem of community detection, see, e.g., [START_REF] Edoardo | Mixed membership stochastic blockmodels[END_REF][START_REF] Zhang | Theoretical and computational guarantees of mean field variational inference for community detection[END_REF][START_REF] Hofman | Bayesian approach to network modularity[END_REF][START_REF] Zahra | Matched bipartite block model with covariates[END_REF]. In particular, the authors of [START_REF] Zhang | Theoretical and computational guarantees of mean field variational inference for community detection[END_REF] show that an iterative Batch Coordinate Ascent Variational Inference algorithm designed for the two-parameters, assortative stochastic block model achieves statistical optimality for community detection problem. Note that this algorithm cannot be extended to the more general stochastic block model considered here.

In parallel with this line of work, the problem of statistical estimation of model parameters, in particular, the question of minimax optimal convergence rates, has been actively studied in the statistical community. In the case of dense graphs, a pioneering paper [START_REF] Gao | Rate-optimal graphon estimation[END_REF] shows that, for the problem of estimating the matrix of connection probabilities, the least square estimator is minimax optimal and [START_REF] Gao | A general framework for Bayes structured linear models[END_REF] provides optimal rate for Bayes estimation. For the more challenging case of sparse graphs, the minimax optimal rates have been first obtained in [START_REF] Klopp | Oracle inequalities for network models and sparse graphon estimation[END_REF] building on the restricted least square estimator. In [START_REF] Gao | Optimal estimation and completion of matrices with biclustering structures[END_REF], the authors consider the least square estimator in the setting when observations about the presence or absence of an edge are missing independently at random with the same probability p. Unfortunately, least square estimation is too computationally expensive to be used in practice. Many other approaches have been proposed, for example, spectral clustering [START_REF] Mcsherry | Spectral partitioning of random graphs[END_REF]21,[START_REF] Rohe | Spectral clustering and the high-dimensional stochastic blockmodel[END_REF], modularity maximization [START_REF] Newman | Modularity and community structure in networks[END_REF][START_REF] Bickel | A nonparametric view of network models and newman-girvan and other modularities[END_REF], belief propagation [START_REF] Decelle | Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications[END_REF], neighbourhood smoothing [START_REF] Zhang | Estimating network edge probabilities by neighbourhood smoothing[END_REF], convex relaxation of k-means clustering [START_REF] Giraud | Partial recovery bounds for clustering with the relaxed K-means[END_REF] and of likelihood maximization [START_REF] Arash | On semidefinite relaxations for the block model[END_REF], and universal singular value thresholding [START_REF] Chatterjee | Matrix estimation by Universal Singular Value Thresholding[END_REF][START_REF] Klopp | Optimal graphon estimation in cut distance[END_REF][START_REF] Xu | Rates of convergence of spectral methods for graphon estimation[END_REF]. These approaches are computationally tractable but show sub-optimal statistical performances. So the question of possible computational gap when no polynomial time algorithm can achieve minimax optimal rate of convergence has been raised.

The present work goes in these two directions. We study the statistical properties of the mean field variational Bayes method and show that it achieves the optimal statistical accuracy. In particular, these results close the open question on the possible existence of a computational gap for the problem of global parameter estimation. We built our analysis on the approach developed in [START_REF] Daudin | A mixture model for random graph[END_REF], [START_REF] Bickel | Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels[END_REF] and [START_REF] Tabouy | Variational inference for stochastic block models from sampled data[END_REF] using the closeness of maximum likelihood and maximum variational likelihood and on the results that show the minimax optimality of the maximum likelihood estimator [START_REF] Gaucher | Maximum likelihood estimation of sparse networks with missing observations[END_REF].

In the present paper, we deal with settings where the network is not fully observed, a common problem when studying real life networks. In many applications the network has missing data as detecting interactions can require significant experimental effort, see, [START_REF] Kshirsagar | Techniques to cope with missing data in host-pathogen protein interaction prediction[END_REF][START_REF] Yan | Finding missing edges in networks based on their community structure[END_REF][START_REF] Handcock | Modeling social networks from sampled data[END_REF][START_REF] Guimerà | Missing and spurious interactions and the reconstruction of complex networks[END_REF]. For example, in biology graphs are used to model interactions between proteins. Discovery of these interactions can be costly and time-consuming [START_REF] Bleakley | Supervised reconstruction of biological networks with local models[END_REF]. On the other hand, the size of some networks from social media or genome sequencing may be so large that only subsamples of the data are considered [START_REF] Benyahia | Community detection in dynamic graphs with missing edges[END_REF]. It has been observed that incomplete observation of the network structure may considerably affect the accuracy of inference methods [START_REF] Kossinets | Effects of missing data in social networks[END_REF] and missing data must be taken into account while analyzing networks data. A popular approach consists in considering the edges with uncertain status as non-existing. In the present paper, we use a different framework by considering such edges as missing and introducing a separated data missing mechanism. A natural application of our method is link prediction [START_REF] Lü | Link prediction in complex networks: A survey[END_REF][START_REF] Zhao | Link prediction for partially observed networks[END_REF], the task of predicting whether two nodes in a network are connected. Our approach allows to deduce the pairs of nodes that are most likely to interact based on the known interactions in the network. Behind inference of the networks structure, our algorithms can be used to predict the links that may appear in the future if we consider networks evolving over the time. For example, in a social network, two users that are not yet connected but are likely to be connected can be recommended as promising friends.

Contribution and outline

The paper is organized as follows. After summarizing notations, we introduce our model and the maximum likelihood estimator for the stochastic block model with missing observations in Section 2. In Section 3, we introduce the mean field variational Bayes method and present a new estimator which combines the labels obtained using the variational method and the empirical mean for estimation of connection probabilities. In Section 3.2, we show that our estimator is minimax optimal for dense stochastic block models with missing observations as well as for sparse stochastic block models. Finally, in Section 4 we provide an extensive numerical study both on synthetic and real-life data which shows clear advantages of our estimator over current methods.

Notations

We provide here a summary of the notations used throughout the paper. For all d ∈ N * , we denote by [d] the set {1, ..., d}. For z :

[k] → [n] and all (a, b) ∈ [d] × [d], we abuse notations and denote z -1 (a, b) = {(i, j) : z(i) = a, z(j) = b, i = j}.
For any two label functions z, z , we write z ∼ z if there exists a permutation σ of {1, ..., k} such that (z(σ(a))) a≤k = (z(a)) a≤k . For any set S, we denote by |S| its cardinality. For any matrix A, we denote by A ij its entry on row i and column j. If A ∈ [0, 1] n×n and A is symmetric, we write A ∈ [0, 1] n×n sym . We denote by A B the Hadamard product of two matrices A and B. The Frobenius norm of a matrix A is denoted by A 2 = i,j A 2 ij . We denote by C and C positive constants that can vary from line to line. These are absolute constants unless otherwise mentioned. For any two positive sequences (a n ) n∈N , (b n ) n∈N , we write

a n = ω(b n ) if a n /b n → ∞.
2 Maximum likelihood estimation in the stochastic block model with missing links

Network model and missing data scheme

In the simplest situation, a network can be represented as undirected, unweighted graph with n nodes indexed from 1 to n. Then, the network can be encoded by its adjacency matrix A = (A ij ). The adjacency matrix is a n × n symmetric matrix such that for any i < j, A ij = 1 if there exists an edge between node i and node j, A ij = 0 otherwise. We consider that there is no edge linking a node to itself, so A ii = 0 for any i. A common approach in network data analysis is to assume that the observations are random variables drawn from a probability distribution over the space of adjacency matrices. More precisely, for i < j the variables A ij are assumed to be independent Bernoulli random variables of parameter Θ * ij , where Θ * = (Θ * ij ) 1≤i<j≤n is a n × n symmetric matrix with zero diagonal entries. The matrix Θ * corresponds to the matrix of probabilities of observing an edge between nodes i and j. This model is known as the inhomogeneous random graph model:

∀1 ≤ i < j ≤ n, A ij |Θ * ij ind. ∼ Bernoulli Θ * ij . ( 1
)
Our focus is on the problem of estimation of the generative matrix Θ * which determines the overall structure of the network. This question is of particular interest for the task of link prediction. Many of real-life networks are characterized by block structure. Loosely speaking, the block structure means that the nodes of the network are partitioned into groups called blocks, and that the distribution of the connections between nodes depends on the blocks to which the nodes belong. For example, when considering citation networks, where two articles are linked if one is cited by the other, it amounts to saying that the probability that two articles are linked only depends on their topic. Similarly, if one considers students of a school in a social network, it is a reasonable assumption to say that the probability that two students are linked only depends on their cohorts.

A very popular model that formalizes this idea is the stochastic block model (see, e.g., [START_REF] Holland | Stochastic blockmodels: First steps[END_REF]). In this model, nodes are classified into k communities: each node i is associated with a community z * (i), where z * : [n] → [k] is called the label function. This label function can either be treated as a parameter to estimate, or as a latent variable. In this last case, it is assumed that the indexes follow a multinomial distribution: ∀i, z * (i) i.i.d ∼ Multinomial(1; α * ) where ∀a ∈ [k], α a is the probability that node i belongs to the community a. Given this label function, the probability that there exists an edge between nodes i and j depends only on the communities of i and j. Thus, the matrix of connection probabilities Θ * can be factorized as follows:

Θ * ij = Q * z * (i)z * (j)
, with Q * a k × k symmetric matrix such that Q * ab is the probability that there exists an edge between a given member of the community a and a given member of the community b. The conditional stochastic block model can be written as:

∃Q * ∈ [0, 1] k×k sym , ∃z * : [n] → [k] ∀1 ≤ i < j ≤ n, A ij | (Q * , z * ) ind. ∼ Bernoulli Q * z * (i)z * (j) , A ii = 0. (2)
Assuming that the network follows the stochastic block model, the problem of estimating the matrix of connection probabilities reduces to estimating the label function z * and the matrix of probabilities of connections between communities Q * . Note that the conditional stochastic block model is at best identifiable up to a simultaneous permutation of the communities and of the rows and columns of the parameters Q * . The stochastic block model has attracted considerable interest from the learning community. An important line of work has focused on the problem of estimation of the latent variables z * , see, for example, [START_REF] Massoulié | Community detection thresholds and the weak ramanujan property[END_REF][START_REF] Bordenave | Nonbacktracking spectrum of random graphs: Community detection and nonregular Ramanujan graphs[END_REF][START_REF] Abbe | Community detection in general stochastic block models: Fundamental limits and efficient algorithms for recovery[END_REF][START_REF] Mossel | Consistency thresholds for the planted bisection model[END_REF]. The best understood framework is the binary, balanced, symmetric, assortative block model. In this simpler model, the two communities have the same size, the same probability of intra-community connection (Q * 11 = Q * 22 = p), and nodes are assumed to be more connected with nodes of the same community (p > q = Q * 12 ). Much work has been done on the precise characterisation of the conditions on p, q that allow for strong recovery of z * , i.e. to estimate z * exactly with high probability. Closest to model ( 2) is perhaps the setting considered in [START_REF] Dhara | Spectral recovery of binary censored block models[END_REF]. In this work, the authors consider the related problem of community recovery in the binary block model [START_REF] Hajek | Exact recovery threshold in the binary censored block model[END_REF], [START_REF] Abbe | Decoding binary node labels from censored edge measurements: Phase transition and efficient recovery[END_REF], and provide tight bounds on the recovery threshold for the balanced, two communities stochastic block model with missing observations. They propose a computationally efficient algorithm for estimating z * in regime where strong recovery is possible; this, however requires prior knowledge of the parameter Q * .

Missing observations scheme Usually, when working with network data, not all the edges are observed. To account for this situation we introduce X ∈ {0, 1} n×n sym the known sampling matrix where X ij = 1 if A ij is observed and X ij = 0 otherwise. We assume that X is random and independent from the adjacency matrix A and its expectation Θ * . For any 1 ≤ i < j ≤ n, its entries X ij are mutually independent and

X ij ind.
∼ Bernoulli(p) for some sampling rate p → 0 such that p = ω (log(n)/n) when n → ∞.

Conditional maximum likelihood estimator

The log-likelihood of the parameters (z, Q) with respect to the adjacency matrix A and the sampling matrix X is given by

L X (A; z, Q) = 1≤i<j≤n X ij A ij log(Q z(i)z(j) ) + (1 -A ij ) log(1 -Q z(i)z(j) ) = a≤b log(Q ab ) (i,j)∈z -1 (a,b) X ij A ij + a≤b log(1 -Q ab ) (i,j)∈z -1 (a,b) X ij (1 -A ij ).
Let us denote by Z n,k the set of all label functions z : [n] → [k]. For a given label function z ∈ Z n,k , the log-likelihood is maximized by taking

Q ab = (i,j)∈z -1 (a,b) X ij A ij (i,j)∈z -1 (a,b) X ij .
It is interesting to note that, for a fixed label function z, maximizing the likelihood or minimizing the least square criterion defined as

C X (A; z, Q) = i<j X ij A ij -Q z(i),z(j) 2
yields the same estimator for the matrix Q. The main difference between these two methods is rooted in the label functions selected by the two criteria, see, e.g. [START_REF] Gaucher | Maximum likelihood estimation of sparse networks with missing observations[END_REF].

To bound the risk of the maximum likelihood estimator, it is usual to assume that there exists sequences ρ n and γ n such that ∀i < j,

0 < γ n ≤ Θ * ij ≤ ρ n < 1. (3)
This assumption ensures that the loss associated to the maximum likelihood estimator is Lipschitz continuous. See, for example, [START_REF] Bickel | Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels[END_REF] and [START_REF] Wang | Likelihood-based model selection for stochastic block models[END_REF], where the authors assume that the adjacency matrix is generated by an homogeneous stochastic block model for which the matrix Q * /ρ n has entries bounded away from 0. The restricted maximum likelihood estimator, Θ, is based on the maximization of the likelihood among block constant matrices with entries in [γ n , ρ n ]:

Θ i<j = Q z(i) z(j) , Θ ii = 0 ( Q, z) ∈ arg max Q∈[γn,ρn] k×k sym ,z∈Z n,k L X (A; z, Q). (4)
In ( 4), γ n and ρ n are assumed to be known (see [START_REF] Gaucher | Maximum likelihood estimation of sparse networks with missing observations[END_REF] for a discussion on how to estimate these parameters). Note that the Expectation-Maximization algorithm used in practice to obtain the variational approximation to the maximum likelihood estimator does not require the knowledge of these parameters. We also assume that k is known and that it can depend on the number of nodes n; it can be chosen using a network cross-validation method [START_REF] Chen | Network cross-validation for determining the number of communities in network data[END_REF], a sequential goodness-of-fit testing procedure [START_REF] Lei | A goodness-of-fit test for stochastic block models[END_REF] or a likelihood-based model selection method [START_REF] Wang | Likelihood-based model selection for stochastic block models[END_REF]. The following result provides the upper bound on the estimation risk of the maximum likelihood estimator:

Theorem 1 (Corollary 2 in [START_REF] Gaucher | Maximum likelihood estimation of sparse networks with missing observations[END_REF]). Assume that A is drawn according to the conditional stochastic block model and ρ n = ω(n -1 ). Then, there exists absolute constants C, C > 0 such that, with probability at least

1 -9 exp -Cρ n k 2 + n log(k) , Θ * -Θ 2 2 ≤ C ρ 2 n ((1-ρn) 2 ∧γ 2 n ) ρ n k 2 + n log(k) p . (5)
When all network entries are observed, we have p = 1. Note that this results implies that, when ρ n = O(γ n ), the maximum likelihood estimator is minimax optimal (see, [START_REF] Klopp | Oracle inequalities for network models and sparse graphon estimation[END_REF][START_REF] Gao | Optimal estimation and completion of matrices with biclustering structures[END_REF] for a statement of the lower bound).

3 Variational approximation to the maximum likelihood estimator

Definition of the estimator

The optimization of the log-likelihood function L X requires a search over the set of k n labels. As a consequence, the maximum likelihood estimator defined in ( 4) is computationally intractable. Celisse et al. [START_REF] Daudin | A mixture model for random graph[END_REF] and Bickel et al. [START_REF] Bickel | Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels[END_REF] are the first to study a variational approximation to this estimator. More recently, the authors of [START_REF] Tabouy | Variational inference for stochastic block models from sampled data[END_REF] used variational methods to approximate the maximum likelihood estimator in networks with missing observations. We start by formally introducing the variational approximation to the maximum likelihood estimator. We consider a stochastic block model with random labels with parameters (α, Q). For this model, the likelihood of the observed adjacency matrix A and sampling matrix X is given by

l X (A; α, Q) = z∈Z n,k   i≤n α z(i)   exp (L X (A; z, Q)) .
Note that the maximization of l X still requires to evaluate the expectation of the label function z for given parameters (α, Q) by summing over k n possible labels. To circumvent this problem, one can use the mean-field approximation, which amounts to approximating the posterior distribution P (•|X A, α, Q) by a product distribution. To ensure that this product distribution remains close to the posterior distribution, the objective function is penalized by the Kullback-Leibler divergence of the two distributions. More precisely, the posterior distribution P (•|X A, α, Q) is approximated by a multinomial distribution denoted P τ , such that P τ (z) = 1≤i≤n m(z|τ i ), where m(•|τ i ) is the density of the multinomial distribution with parameter τ i = τ i 1 , ..., τ i k , and τ = τ 1 , ..., τ n . Then, the variational estimator is defined as

α V AR , Q V AR , τ V AR = arg max α∈A,Q∈Q,τ ∈T J X (A; τ, α, Q) (6) for J X (A; τ, α, Q) = log (l X (A; α, Q)) -KL (P τ (•)||P (•|X A, α, Q))
where A, Q and T are the respective parameter spaces for the parameters α, Q and τ , KL denotes the Kullback-Leibler divergence between two distributions, and X A denotes the observed entries of A. Since for any parameter (α, Q),

KL (P τ (•)||P (•|X A, α, Q)) ≥ 0, we see that exp (J X (A; τ, α, Q)) provides a lower bound on l X (A; α, Q).
The expectation -maximization (EM) algorithm derived in [START_REF] Tabouy | Variational inference for stochastic block models from sampled data[END_REF] can be used to iteratively approximate the variational estimator. This algorithm alternates between the following two steps :

• Estimation Step: given parameters (α, Q), the variational parameter τ maximizing J X (A; τ, α, Q) is
given by the fixed point equation :

τ i a = c i α a j =i:Xij =1 b≤k Q Aij ab (1 -Q ab ) 1-Aij τ j b
where c i is a normalizing constant;

• Maximization Step: given parameter τ , the parameters (α, Q) maximizing J X (A; τ, α, Q) are given by

α a = i τ i a n , Q ab = i =j X ij τ i a τ j b A ij i =j X ij τ i a τ j b .
Since this algorithm is not guaranteed to converge to a global maximum, it should be initialized with care, by using, for example, a first clustering step. This solution is implemented in the package missSBM.

Statistical guarantees for the variational estimator obtained in [START_REF] Daudin | A mixture model for random graph[END_REF][START_REF] Bickel | Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels[END_REF][START_REF] Mariadassou | Consistency and asymptotic normality of stochastic block models estimators from sampled data[END_REF] establish that maximizing max τ ∈T J X (A; τ, α, Q) is equivalent to maximizing l X (A; α, Q), and that the estimator obtained by maximizing l X (A; α, Q) converges to the true parameters (α * , Q * ). This in turn implies that ( α

V AR , Q V AR
) also converges to (α * , Q * ). Note that these results do not provide guarantees on the recovery of the true labels z * or on the matrix of connection probabilities Θ * . In order to estimate Θ * , we first define the label estimator z V AR using the minimizer of the objective function [START_REF] Bickel | Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels[END_REF]:

∀ i ≤ n, z V AR (i) arg max a≤k τ V AR i a . (7)
Once we have estimated the community labels using [START_REF] Bickel | A nonparametric view of network models and newman-girvan and other modularities[END_REF], we replace the estimator Q

V AR
of the matrix of connection probabilities by the empirical mean estimator:

∀a < k and b < k, Q M L-V AR ab (i,j)∈( z V AR ) -1 (a,b) X ij A ij (i,j)∈( z V AR ) -1 (a,b) X ij and define Θ V AR as Θ V AR i =j = Q M L-V AR z V AR (i), z V AR (j) , Θ V AR ii = 0. ( 8
)
We will show respectively in Theorems 2 and 3 that this new estimator

z V AR , Q M L-V AR
is minimax optimal for dense networks with missing observations as well as for sparse networks. The simulation study provided in Section 4 reveals that this estimator also has good performances in practice.

Convergence rates of variational approximation to the maximum likelihood estimator

In this section, we show the asymptotic equivalence of z V AR and z, where

( Q, z) ∈ arg max Q∈Q,z∈Z n,k L X (A; z, Q) (9)
is the maximum likelihood estimator. More precisely, we show that, with large probability, there exists a permutation σ of {1, ..., k} such that z V AR (σ(a)) a≤k = (z(a)) a≤k and

Q M L-V AR σ(a),σ(b) a,b≤k = Q a,b a,b≤k .
When this hold, the tractable estimator

z V AR , Q M L-V AR
is minimax optimal. These results are established under the following assumptions:

A.1 There exists c > 0 and a compact interval

C Q ⊂ (0, 1) such that A ⊂ [c, 1 -c] and Q ⊂ C k×k Q ; A.2
The true parameters α * and Q * lie respectively in the interior of A and Q;

A.3 The coordinates of α * Q * are pairwise distinct.

Note that Assumption A.2 and A.3 are standard. Assumption A.2 requires that the true parameters lie in the interior of the parameter space, which is classical in parametric estimation. In the most simple case, the parameters α * and Q * lie respectively in the interior of sets A and

Q of the form A = [c, 1 -c], Q = [c , 1 -c ] k×k
sym , for some c, c ∈ (0, 1/2). Assumption A.3 ensures the identifiability of stochastic block model parameters. Then, under the assumption that p = ω (n/ log(n)), strong recovery of the labels is possible. Assumption A.1 is more restrictive, as it implies that the network is dense. This assumption will be relaxed in Theorem 3, where we consider sparse stochastic block models such that Q * = ρ n Q 0 for some fixed Q 0 and some decreasing, sparsity inducing sequence ρ n .

The following Theorem shows the minimax optimality of the tractable estimator Θ V AR under assumptions A.1 -A.3.

Theorem 2. Assume that A is generated from a stochastic block model with parameters (α * , Q * ) satisfying assumptions A.1 -A.3. Then, P z V AR ∼ z → 1 when n → ∞. Moreover, there exists a constant C Q * > 0 depending on Q * such that

P Θ * -Θ V AR 2 2 ≤ C Q * k 2 + n log(k) p → n→∞ 1.
Let us now discuss the extension of Theorem 2 to the case of sparse networks. To avoid technicalities, we will consider the case when the network is fully observed. We will also assume that the proportions of different communities are held constant, while the probabilities of connections between communities may decreases at rate ρ n . That is, the parameters (α * , Q * ) verify the following assumptions:

A.4 α * = α 0 for some fixed α 0 such that α 0 a > 0 for any a ∈ {1, ..., k}

A.5 Q * = ρ n Q 0 for some fixed Q 0 ∈ (0, 1) k×k such that k a,b=1 α 0 a α 0 b Q 0 ab = 1
Assumption A.5 relaxes Assumption A.1 and allows us consider sparse networks. The normalization constraint 1≤a,b≤k α 0 a α 0 b Q 0 ab = 1 ensure the identifiability of the parameters (Q 0 , ρ n ) (see [START_REF] Bickel | Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels[END_REF]). In the following, we denote by Q the set of parameters (α, Q) verifying Assumptions A.4 and A.5.

The following theorem provides the analogous of Theorem 2 in the case of fully observed sparse networks. It is obtained by combining Propositions 2 and 3 in [START_REF] Gaucher | Maximum likelihood estimation of sparse networks with missing observations[END_REF]: Theorem 3. Assume that A is fully observed, and is generated from a stochastic block model with parameters (α * , Q * ) satisfying Assumptions A.4 and A.5, such that Q 0 has no identical columns and the sparsity inducing sequence ρ n satisfies ρ n log(n)/n. Then, P z V AR ∼ z → 1 when n → ∞. Moreover, there exists a constant C Q 0 > 0 depending on Q 0 such that

P Θ * -Θ V AR 2 2 ≤ C Q 0 ρ n k 2 + n log(k) → n→∞ 1. ( 10
)
Theorems 2 and 3 establish that the variational estimator

Θ V AR
is minimax optimal for both the estimation of dense networks with observations missing uniformly at random, and sparse networks. For proofs and discussion see Appendix B.1.

Numerical Results

Synthetic data

In this section we provide a simulation study of the performances of the maximum likelihood estimator defined in [START_REF] Bleakley | Supervised reconstruction of biological networks with local models[END_REF], and compare it to the variational estimator defined in [START_REF] Tabouy | Variational inference for stochastic block models from sampled data[END_REF] and implemented in the package missSBM, as well as to the Universal Singular Value Thresholding estimator introduced in [START_REF] Hastie | Matrix completion and low-rank svd via fast alternating least squares[END_REF] and implemented in the package softImpute. The results are reported in Figure 1. Thorough descriptions of the simulation protocols are provided in the Appendix.

Dense stochastic block model First, we evaluate the empirical performances of the variational approximation of the maximum likelihood estimator defined in (8) on dense stochastic block models. We estimate the matrix of probabilities of connections, and we compare our estimator with the estimator given by the methods missSBM and softImpute. The quality of the inference is assessed by computing the squared Frobenius distance between the estimators and the true matrix of connection probabilities Θ * .

We consider three types of three-communities stochastic block model. The first model, given by (α assort. , Q assort. ), provides a simple assortative network, where individuals are more connected with people from their communities than with other individuals. On the contrary, the second model, given by (α disassort. , Q disassort. ), is disassortative: individuals are more connected with individuals from outside of their communities. Both the assortative and disassortative models have balanced communities. The third model considered, given by (α mix. , Q mix. ), exhibits neither assortativity nor disassortativity, and the communities are unbalanced. We introduce missing data by observing each entry of the adjacency matrix independently with probability 0.5.

The variational approximation to the maximum likelihood estimator defined in (8) outperforms the softImpute method across all models and all number of nodes. Its error is equivalent to that of the oracle estimator with hindsight knowledge of the true label function z * when the network is a few hundred nodes large. Interestingly, our estimator also outperforms the variational estimator implement in the package missSBM. We underline however that the primary focus of the missSBM method is to infer the parameters (α * , Q * ). Additional experiments illustrating the strong consistency of the variational estimator canbe found in Appendix B.2.

Sparse stochastic block model Next, we investigate the behaviour of our estimator on increasingly sparse networks. We consider a three-communities assortative stochastic block model of 500 nodes with balanced communities, and 50% missing values. The probabilities of connections are given by Q * = ρQ 0 , where ρ is a parameter controlling the sparsity, which ranges from 0.05 to 1. We compare the performance of the variational approximation to the maximum likelihood estimator to that of the methods softImpute and missSBM. We also compare these estimators to the trivial estimator with all entries equal to the average degree divided by the number of nodes. The error is measured as the squared Frobenius distance between the estimator and the matrix Θ * divided by ρ 2 .

As the network sparsity increases, the clustering of the nodes becomes more difficult. The normalized error of the estimator Θ V AR increases up to a threshold corresponding to the normalized error of the trivial estimator with all entries equal to the empirical degree, divided by the number of nodes. Note that when considering very sparse networks, with ρ log(n)/n, it is known that the trivial estimator with entries equal to the empirical mean degree is minimax optimal (see, eg, [START_REF] Klopp | Oracle inequalities for network models and sparse graphon estimation[END_REF])). Thus, the estimator enjoys relatively low error rates in both high and low signal regime. By contrast, the normalized error of the softImpute method diverges as the network becomes increasingly sparse.

Stochastic block model with missing observations

To conclude our simulation study, we evaluate the robustness of the methods against missing observations. We consider a three-communities assortative stochastic block model with balanced communities and 500 nodes. We increase the proportion of missing observations, and we compare the performance of the variational approximation to the maximum likelihood estimator to that of the methods softImpute and missSBM. The error is measured as the squared Frobenius distance between the estimator and the matrix Θ * .

As the sampling rate p decreases, the clustering becomes impossible and the error rate of the estimator

Θ V AR
increases up to that of the trivial estimator obtained by averaging the observed entries of the adjacency matrix. By contrast, the methods softImpute and missSBM lack robustness against missing observations, and their error diverges as the number of missing observations increases.

Analysis of real networks

Prediction of interactions within a elementary school

We apply our algorithm to analyze a network of interactions within a French elementary school collected by the authors of [START_REF] Stehlé | High-resolution measurements of face-to-face contact patterns in a primary school[END_REF]. The network records durations of physical interactions occurring within a primary school between 222 children divided into 10 classes and their 10 teachers over the course of two consecutive days; this dataset was collected using a system of sensors worn by the participants. We consider that an interaction has occurred if the corresponding duration is greater than one minute. If an interaction of less than one minute is observed, we consider that this observation may be erroneous, and treat the corresponding data as missing. By doing so, we remove respectively 11 and 13% of the observations on Day 1 and Day 2.

The graphs of interactions recorded during Day 1 and Day 2 can be considered as two outcomes of the same random network model characterized by the matrix of connection probabilities Θ * . In this spirit, we use the observations collected on Day 1 estimate the matrix Θ * , and evaluate those estimators on the network of interactions corresponding to Day 2. We note that the network of interactions for Day 1 has rather homogeneous degrees (the maximum degree is 41 and the minimum degree is 5, while the mean degree is 20). Moreover, it exhibits a strong community structure. Therefore, we expect the networks of interactions to be well approximated by a stochastic block model.

We compare the performance in terms of link prediction of the estimator Θ V AR defined in [START_REF] Bleakley | Supervised reconstruction of biological networks with local models[END_REF] to that of the method missSBM, and that of the method softImpute. In this last method, we set the penalty to 0, and we choose the rank of the estimator to be equal to the number of communities, which is estimated according to the Integrated Likelihood Criterion. We also compare these methods to the naive persistent estimator Θ naive given by Θ naive ij = 1 if an interaction between i and j has been recorded on Day 1, Θ naive = 0 if no such interaction has been recorded, and Θ naive ij = d/n if the information is missing, where d is the average degree of the graph for Day 1. Table 1 present the error of the different estimators, measured as the squared Frobenius distance between the adjacency matrix of Day 2 and its predicted value, divided by the squared Frobenius norm of the adjacency matrix of Day 2 (i.e, the error of the trivial null estimator).

The variational method predicts most accurately the interactions on Day 2. It is closely followed by the estimator provided by the package missSBM. By contrast to the simulation study, the reduction in error when using the new estimator is moderate : the error of Θ V AR is respectively 1.4% and 12.4% smaller than that of Θ missSBM and Θ sof tImpute . In addition, the precision-recall curve presented in the Appendix indicates Estimator that no estimator is better across all sensitivity levels. Interestingly, the naive estimator obtains a high error, which suggests a certain versatility in the children's behaviour.

Θ V AR Θ missSBM Θ SV T Θ naive X (A -Θ)

Network of co-authorship

Finally, we use variational approximation to predict unobserved links in a network of co-authorship between scientists working on network analysis, first analysed in [START_REF] Mark Ej Newman | Finding community structure in networks using the eigenvectors of matrices[END_REF]. We discard the smallest connected components (with less than 5 nodes), and we obtain a network of 892 nodes. By contrast to the network of interaction in an elementary school, the network of co-authorship is quite sparse, and presents heterogeneous degrees: the average number of collaborators is 5, while the maximum and minimum number of collaborators are respectively 37 and 1.

In order to obtain unbiased estimates of the error of the estimators Θ V AR

, softImpute, and missSBM, we introduce 50% of missing values in the dataset. We train the three estimators on the observed entries of the adjacency matrix, and we use the unobserved entries to evaluate their imputation error. Table 2 present the mean imputation error of the different estimators over 100 random samplings, measured in term of squared Frobenius error and normalized by the squared Frobenius norm of the adjacency matrix of the remaining entries (i.e, the error of the null estimator). Here again, the variational approximation to the maximum

Estimator Θ V AR Θ missSBM Θ SV T (1 -X) (A -Θ) 2 2 (1 -X) A 2 2
0.857 0.869 0.894 Table 2: Imputation error of the estimators on the network of co-authorship.

likelihood estimator obtains the best performance. The precision-recall curves of these methods, included in the Appendix, indicates that this new estimator is preferable across almost all sensitivity levels. We underline however that the errors in term of Frobenius norm of the three estimators are close, and relatively high. This comes as no surprise, as the high sparsity of the network causes the link prediction problem to be difficult.

Conclusion

In this work, we have introduced a new tractable estimator based on variational approximation of the maximum likelihood estimator. We show that it enjoys the same convergence rates as the maximum likelihood estimator, and that it is therefore minimax optimal. Our simulation studies reveal the advantages of our estimator over current methods. In particular, they highlight its robustness against network sparsity and missing observations. Our results pave the way for analysing variational approximations of more general structured network models such as the latent block model.

A Proofs

In this section, we prove Theorem 2. This proof follows to some extend that of Theorem 3, so we underline the main differences. Because of missing links, we introduce new techniques to compare the restricted and unrestricted maximum likelihood estimators. We also need to establish the strong consistency of the maximum likelihood estimator for the conditional SBM (in the full observation setting, this result is a direct consequence of [START_REF] Bickel | A nonparametric view of network models and newman-girvan and other modularities[END_REF]). Similarly, the proof of Theorem 3 relies heavily on the fact that the likelihood function at the parameters and the profile likelihood function at the parameters are asymptotically equivalent, which is a direct consequence of Lemma 3 [6]. This result does not hold under missing observations, and we develop new arguments to prove the strong consistency of the variational estimate of the labels.

A.1 Proof of Theorem 2

To prove Theorem 2, we first show that

P •|X A, α V ar , Q V ar
, i.e. the posterior distribution of z at the variational estimator ( α V ar , Q

V ar

), concentrates around δ z , the dirac distribution at some label function z such that z ∼ z * :

P z |X A, α V ar , Q V ar = 1 -o p (1). (11)
Then, we show that it implies the concentration of the estimator z V ar :

P z V ar = z |X A = 1 -o p (1). ( 12
)
Since P z V ar = z |X A is bounded, this also implies that it converges to 1 in expectation :

P z V ar = z → 1. (13)
Finally, we show that with probability going to one,

P ( z ∼ z * ) → 1. (14)
Combing Equations ( 12) and ( 14), we prove the first part of Theorem 2 :

P z ∼ z V AR → 1. (15)
To establish the second part of Theorem 2, we show that the maximum likelihood estimator defined in ( 9) is equal to the restricted maximum estimator (4). Theorem 3 then follows from Theorem 1.

Define

c min = min a,b Q * a,b and c max = max a,b Q * a,b
. Theorem 1 implies that for some absolute constant C > 0,

P Θ * -Θ r 2 2 ≤ C(c max /c min ) 2 k 2 + n log(k) → 1,
where the restricted maximum likelihood estimator Θ r is defined as

Θ r i<j = Q r z r (i) z r (j) , Θ r ii = 0 ( Q r , z r ) ∈ arg max Q∈[cmin/2,2cmax] k×k sym ,z∈Z n,k i =j L X (A ij , Q z(i)z(j) ).
Now, Equation [START_REF] Gao | Optimal estimation and completion of matrices with biclustering structures[END_REF] implies that with probability going to one, the variational estimator of the probabilities of connections Θ

V AR is equal to the maximum likelihood estimator Θ given by

Θ i<j = Q z(i) z(j) , Θ ii = 0 for ( Q, z) ∈ arg min Q∈Q,z∈Z n,k i =j K(A ij , Q z(i)z(j) ). For z ∈ Z n,k , define Λ(z) = max Q∈Q L X (A; z, Q) -L X (A; z * , Q * ) and Λ(z) = max Q∈Q E L X (A; z, Q) -L X (A; z * , Q * ) z * . Moreover, for z ∈ Z n,k and (α, Q), define z -z * ∼,0 = min z :z ∼z * z -z * 0
where z -z * 0 is the Hamming distance between the label functions z and z * . To prove Equation ( 14), we will use the following results.

Proposition 4 (Equation (B.1) in [START_REF] Mariadassou | Consistency and asymptotic normality of stochastic block models estimators from sampled data[END_REF]). There exists a constant c > 0 such that on an event of probability going to one, for all positive sequence (t n ) n∈N such that t n → 0 and

pnt n / log(n) → +∞, ∀z / ∈ S(z * , t n ), Λ(z) ≤ - 3cpn 2 t n δ(Q * ) 4
where and

δ(Q) = min a,a max c KL (Q ac , Q a c ) and S(z * , t n ) = z ∈ Z n,k : z -z * ∼,0 ≤ nt n .
Proposition 5 (Proposition 6.7 in [START_REF] Mariadassou | Consistency and asymptotic normality of stochastic block models estimators from sampled data[END_REF]). There exists a constant C Q > 0 depending on Q such that for any sequence

( n ) n∈N with n < C Q and n ≥ k 2 /( √ 8n), sup z∈Z n,k Λ(z) -Λ(z) = O p ( n n 2 ).
We choose n = 3δ(Q * ) log(n)/(8n). Then, Proposition 5 implies that there exists a constant C > 0 such that with probability going to 1, sup

z∈Z n,k Λ(z) -Λ(z) ≤ C n n 2 .
Λ(z) -Λ(z) ≤ - 3Cpn 2 t n δ(Q * ) 4 + 3Cpn 2 t n δ(Q * ) 8 ≤ - 3Cn log(n)δ(Q * ) 8 .
This implies in particular that

P sup z / ∈S(z * ,tn) Λ(z) < 0 → 1. ( 21
)
We show a similar result for label functions z that are close to z * . To do so, we use the following result.

Proposition 6 (Proposition 6.5 in [START_REF] Mariadassou | Consistency and asymptotic normality of stochastic block models estimators from sampled data[END_REF]). There exists a positive constant C such that on an event of probability going to 1, for all z ∈ S(z * , C),

Λ(z) ≤ - 3cpn 2 δ(Q * ) z -z * ∼,0 4
.

We use Proposition 4, where we choose n = k 2 /n. Then, there exists a constant C > 0 such that with probability going to 1, sup z∈Z n,k Λ(z) -Λ(z) ≤ C nk 2 . Now, Proposition 6 implies that with probability going to 1, sup

z∈S(z * ,C),z ∼z * Λ(z) ≤ sup z∈S(z * ,C),z ∼z * Λ(z) + sup z∈S(z * ,C),z ∼z * Λ(z) -Λ(z) ≤ - 3cpn 2 δ(Q * ) 4 + C nk 2 ≤ nk 2 C - 3cpnδ(Q * ) 8k 2 .
Since pn → +∞, this implies that

P sup z∈S(z * ,C),z ∼z * Λ(z) < 0 → 1. (22)
Finally, since t n → 0, for n large enough Z n,k = S(z * , C) ∪ S(z * , t n ). Thus, Equations ( 21) and ( 23) imply that

P sup z ∼z * Λ(z) < 0 → 1. ( 23
)
Now, Λ(z * ) = 0. Thus, with probability going to 1, arg max Λ(z) ∼ z * , so z ∼ z * .

Proof of Equation (16)

To prove Equation ( 16), we use Bernstein's inequality, which we recall here for sake of completeness :

Theorem 4 (Bernstein's inequality). Let X 1 , ..., X n be independent centered random variables. Assume that for any i ∈

[n], |X i | ≤ M almost surely, then P   1≤i≤n X i ≥ 2t 1≤i≤n E[X 2 i ] + 2M 3 t   ≤ 2e -t . For z ∈ Z n,k and (a, b) ∈ [k] 2 , define n ab (z) = |(z) -1 (a)| × |(z) -1 (b)| if a = b |(z) -1 (a)| × |(z) -1 (a)| -1 otherwise and n X ab (z) = i∈z -1 (a),j∈z -1 (b) i =j X ij
the number of entries and of observed entries of the adjacency matrix between nodes of the communities a and b, and

Q(z) = (Q(z) ab ) such that Q(z) ab = i∈z -1 (a),j∈z -1 (b) X ij A ij /n X ab (z). With these notations, we note that Q = Q( z). Note that |(z * ) -1 (a)
| is a sum of n independent Bernoulli random variables with mean α a . Using Bernstein's inequality 4, we find that for any a, Now, we show that on the event Ω , with large probability, Q(z * ) ∈ [c min /2, 2c max ] k×k . Recall that for any a, b, conditionally on z * and X, n X ab (z * )Q(z * ) ab is a sum of n X ab (z * ) independent Bernoulli random variables with mean Q * ab . Then, Bernstein's inequality implies that for any t > 0

P nα a -|(z * ) -1 (a)| ≥ 0.
P n X ab (z * )Q(z * ) ab -n X ab (z * )Q * ab ≥ 2tn X ab (z * )Q * ab + 2t 3 z * , X ≤ 2e -t . Choosing t = n X ab (z * )Q * ab /16 yields P n X ab (z * )Q(z * ) ab -n X ab (z * )Q * ab ≥ 0.5n X ab (z * )Q * ab z * , X ≤ 2e -n X ab (z * )Q * ab /16 .
On the event Ω , this implies that

P |Q(z * ) ab -Q * ab | ≥ 0.5Q * ab Ω ≤ 2e -n 2 Q * ab (mina αa) 2 /160 .
A union bound yields

P Q(z * ) / ∈ [c min /2, 2c max ] k×k Ω ≤ 2k 2 e -n 2 min a,b Q * ab (mina αa) 2 /160 .
Since P (Ω ) → 1, this shows that

P Q(z * ) ∈ [c min /2, 2c max ] k×k → 1.
Now, Equation [START_REF] Dhara | Spectral recovery of binary censored block models[END_REF] shows that with probability going to 1, z ∼ z * . Thus,

P Q( z) ∈ [c min /2, 2c max ] k×k → 1.

A.2 Proof of Theorem 3

In the case of fully observed network, we alleviate notations and write

L(A; z, Q) = i =j A ij log Q z(i),z(j) + (1 -A ij ) log 1 -Q z(i),z(j) , l (A; α, Q) = z∈Z n,k i α z(i) exp (L(A; z, Q)) , and
J (A; τ, α, Q) = log (l (A; α, Q)) -KL (P τ (•) ||P (•|A, α, Q)) .
For any z ∈ Z n,k and (α, Q) ∈ Q, we denote

l (A, z; α, Q) =   i≤n α z(i)   exp (L(A; z, Q))
the likelihood of the parameters (α, Q) and the label function z. Then, the likelihood of the stochastic block model with parameters (α, Q) is given by l (A; α, Q) = z∈Z n,k l (A, z; α, Q). Note that the likelihood Proof of Equation (28) To do so, we show that with large probability, Q

( z) ∈ [c min ρ n /2, 2c max ρ n ] k×k ]. We define n ab (z) = |z -1 (a)| × |z -1 (b)| if a = b |z -1 (a)| × |z -1 (a)| -1 otherwise for z ∈ Z n,k , and Q(z) = (Q(z) ab ) such that Q(z) ab = i∈z -1 (a),j∈z -1 (b)
A ij /n ab (z). With these notations, we note that Q = Q( z).

Recall that |(z * ) -1 (a)| is a sum of n independent Bernoulli random variables with mean α 0 a . Using Bernstein's inequality 4, we find that for any a,

P nα 0 a -|(z * ) -1 (a)| ≥ 0.5nα 0 a ≤ 2e -nα 0 a /16 .
Thus,

P min a |(z * ) -1 (a)| ≤ 0.5n min a α 0 a ≤ 2ke -n mina α 0 a /16 .
Therefore, the event Ω = min a,b n a,b (z * ) ≥ n 2 min a (α 0 a ) 2 /5 holds with probability going to 1. Now, we show that on the event Ω, with large probability, Q(z * ) ∈ [c min ρ n /2, 2c max ρ n ] k×k . Recall that for any a, b, conditionally on z * , n ab (z * )Q(z * ) ab is a sum of n ab (z * ) independent Bernoulli random variables with mean ρ n Q 0 ab . Then, Bernstein's inequality 4 implies that for any t > 0

P n ab (z * )Q(z * ) ab -n ab (z * )ρ n Q 0 ab ≥ 2tn ab (z * )ρ n Q 0 ab + 2t 3 ≤ 2e -t . Choosing t = n ab (z * )ρ n Q 0 ab /16 yields P n ab (z * )Q(z * ) ab -n ab (z * )ρ n Q 0 ab ≥ 0.5n ab (z * )ρ n Q 0 ab ≤ 2e -n ab (z * )ρnQ 0 ab /16 .
On the event Ω, this implies that

P n ab (z * )Q(z * ) ab -n ab (z * )ρ n Q 0 ab ≥ 0.5n ab (z * )ρ n Q 0 ab ≤ 2e -n 2 ρnQ 0 ab (mina α 0 a ) 2 /80 .
A union bound yields

P Q(z * ) / ∈ [c min ρ n /2, 2c max ρ n ] k×k ≤ 2k 2 e -n 2 ρn min a,b Q 0 ab (mina α 0 a ) 2 /80
on the event Ω. Since P (Ω) → 1 and n 2 ρ n → +∞, this shows that

P Q(z * ) ∈ [c min ρ n /2, 2c max ρ n ] k×k → 1.
Now, Equation [START_REF] Michael | An introduction to variational methods for graphical models[END_REF] shows that with probability going to 1, z ∼ z * . Thus, Q( z) ∈ [c min ρ n /2, 2c max ρ n ] k×k with probability going to one, and the maximum likelihood estimator of the probabilities of connections between nodes coincides with the restricted maximum likelihood estimator. This concludes the proof of Equation ( 28).

B Further informations on the numerical experiments B.1 Simulation protocol

In this section, we provide details on the simulation protocol for Section 4. For each model and each number of nodes, we simulate 100 networks. For each networks, entries of the adjacency matrix are observed independently from one another with probability 1/2. Then, the matrix of connection probabilities Θ * is estimated using each method (variational approximation to the maximum likelihood estimator, missSBM, and softImpute). The oracle estimator is obtained as

∀a < k and b < k, Q * ab i∈(z * ) -1 (a),j∈(z * ) -1 (b),i =j X ij A ij i∈(z * ) -1 (a),j∈(z * ) -1 (b),i =j X ij
Sparse stochastic block model The parameters (α, Q) of the stochastic block model are given by α = (1/3, 1/3, 1/3), and

Q = ρ   0.5 0.2 0.2 0.2 0.5 0.2 0.2 0.2 0.5  
for ρ ranging between 0.05 and 1. For each sparsity, we simulate 100 networks with 500 nodes. For each networks, entries of the adjacency matrix are observed independently from one another with probability 1/2. Then, the matrix of connection probabilities Θ * is estimated using each method (variational approximation to the maximum likelihood estimator, missSBM, softImpute, the oracle estimator and the naive estimator). The proportion of observed entries p varies between 0.02 and 1. For each p, we simulate 100 networks with 500 nodes. For each networks, entries of the adjacency matrix are observed independently from one another with probability p. Then, the matrix of connection probabilities Θ * is estimated using each method (variational approximation to the maximum likelihood estimator, missSBM, softImpute, the oracle estimator and the naive estimator).

Stochastic block model with missing observations

B.2 Empirical strong consistency of the variational estimator

We illustrate the empirical strong consistency of the variational estimator. Using the parameters chosen for simulating dense stochastic block models, we compute the number of misclassified nodes, defined as min z∼ẑ i

1 {z * (i) = z(i)} .

The total classification error for the assortative, dissasortartive and mixed models are presented in Figure 2. These simulations confirm that the variational estimator achieves strong recovery of the labels, even in unbalanced setting when neither assortative or disassortative behaviour are observed.

B.3 Prediction of interactions within an elementary school

To compare the errors in term of link prediction of the methods missSBM and softImpute with that of our estimator, we plot the precision-recall curves of these estimators. More precisely, for any estimator Θ of the matrix of connection probabilities Θ * , and all thresholds t ∈ [0, 1], one can define the link-prediction estimator A as follows : A ij = 1 if and only if Θ ij ≥ t, that is, we predict that there exists a link between nodes i and j is the estimated probability that these nodes are connected is larger than the threshold t. The recall-precision curves obtained by varying this threshold is presented in Figure 3. We also represent the mean precision-recall curve of the baseline estimator obtained by predicting edges independently at random with an increasing probability. The three methods used for link prediction obtain quite similar precision-recall curves. No single method is better across all sensitivity levels.

B.4 Prediction of collaboration in the co-authorship network

Similarly, we plot the precision-recall curves of the link-prediction methods obtained by using our new estimator, missSBM and softImpute. We also represent the mean precision-recall curve of the baseline estimator obtained by predicting edges independently at random with an increasing probability. The recall-precision curves is presented in Figure 4.

The precision-recall curve of the variational approximation to the maximum likelihood estimator is equivalent to or better than the other estimators across all sensitivity levels. Figure 3: Precision-recall curves for link prediction in the network of interactions within a school: Precision-recall curves of the estimator obtained using missSBM (in red), of the estimator obtained using softImpute (in green), and of the variational approximation to the maximum likelihood estimator (in blue). The dotted black line represents the precision of the baseline estimator.

Figure 4: Precision-recall curves for link prediction in the network co-authorship: Precision-recall curves of the estimator obtained using missSBM (in red), of the estimator obtained using softImpute (in green), and of the variational approximation to the maximum likelihood estimator (in blue). The dotted black line represents the precision of the baseline estimator.

  Robustness against sparsity. (e) Robustness against missing observations.

Figure 1 :

 1 Figure 1: Top : Error of connection probabilities estimation as a function of the number of nodes (top left :assortative SBM with balanced communities; top middle : disassortative SBM with balanced communities; top right : mixed SBM with unbalanced communities) or of the sparsity parameter ρ (bottom left) and of the sampling rate p (bottom right). We compare the variational approximation to the maximum likelihood estimator (in blue) to that of missSBM (in red), that of softImpute (in green), that of the oracle estimator with knowledge of the label z * (in black), and that of the trivial estimator with entries equal to the empirical average degree divided by the number of nodes (orange, bottom only). The full lines indicate the median respectively of the mean squared error (top and bottom right) and of the mean squared error divided by the sparsity parameter ρ (bottom left) of the estimators over 100 repetitions, while the dashed lines indicate its 25% and 75% quantiles.

  5nα a ≤ 2e -nαa/16 . * ) -1 (a)| ≤ 0.5n min a α a ≤ 2ke -n mina αa/16 . Therefore, the event Ω = min a,b n a,b (z * ) ≥ n 2 min a (α a ) 2 /5 holds with probability going to 1. Similarly, note that conditionally on z * , n X ab (z * ) is a sum of n ab (z * ) independent Bernoulli variables with parameter p. Then, for any two (a, b) ∈ [k] 2 , Bernstein's inequality 4 implies that P |pn ab (z * ) -n X ab (z * )| ≥ 0.5pn ab (z * ) z * ≤ 2e -pn ab (z * )/16 . (z * ) ≤ 0.5p min a,b n ab (z * ) z * ≤ 2ke -p min a,b n ab (z * )/16 . This implies that P min a,b n X ab (z * ) ≤ 0.1n 2 p min a α 2 a Ω ≤ 2ke -pn 2 mina αa/80 . Since p log(n)/n, the event Ω = {∀(a, b) ∈ [k] 2 , n X ab (z * ) ≥ 0.1n 2 p min a α 2 a } holds with probability going to 1.

1 .

 1 The numerical experiments where conducted using R version 4.0.3, the package softImpute version 1.4.1, and the package missSBM version 0.3.0.Dense stochastic block model The parameters used for the simulations are the following : α assort. = α disassort. = (1/3, 1/3, 1/3), α mix. = (0.1, 0.3, 0.6), andQ assort.

  The parameters (α, Q) of the stochastic block model are given by α = (1/3, 1/3, 1/3), and

Figure 2 :

 2 Figure 2: Number of nodes misclassified by the variational estimator in the assortative SBM with balanced communities (left), in the disassortative SBM with balanced communities (middle), and in the mixed SBM with unbalanced communities (right). The full lines indicate the median of the number of misclassified nodes over 100 repetitions, while the dashed lines indicate its 25% and 75% quantiles.

Table 1 :

 1 Link prediction error on the network of interactions within a primary school.

	2 2	X A 2 2	0.312	0.317	0.357	0.541

  Moreover, we choose t n =

	2C log(n)/(cnp) and note that under the assumption p	log(n)/n, t n → 0. Then, Propositions 4 and 5
	imply that with probability going to one
	sup	Λ(z) ≤	sup	Λ(z) + sup
	z / ∈S(z * ,tn)		z / ∈S(z * ,tn)		z / ∈S(z

* ,tn)

Acknowledgments

We thank the anonymous referees for their helpfull comments.

Thus, it is enough to show that Θ = Θ r with large probability to prove the second part of Theorem 3. To do so, we show that P Q( z) ∈ [c min /2, 2c max ] k×k → 1. ( 16)

Equation [START_REF] Gao | Rate-optimal graphon estimation[END_REF] implies that with probability going to 1, the maximum likelihood estimator of the probabilities of connections between nodes coincides Θ with the restricted maximum likelihood estimator Θ r . This concludes the proof of Theorem 3. [START_REF] Chen | Network cross-validation for determining the number of communities in network data[END_REF] For any z ∈ Z n,k and (α, Q) ∈ Q, let l X (A, z; α, Q) = i≤n α z(i) exp (L X (A; z, Q)) be the profile likelihood of the parameters (z, Q). Then,

Proof of Equation

Let z = arg max z:z∼z * l X A, z; α V AR , Q

V AR

. By definition of l X ,

On the one hand, we bound the sum

using the following result, proven in [START_REF] Mariadassou | Consistency and asymptotic normality of stochastic block models estimators from sampled data[END_REF] :

Proposition 1 (Proposition 6.11 in [START_REF] Mariadassou | Consistency and asymptotic normality of stochastic block models estimators from sampled data[END_REF]). For any ) exhibits no symmetry, i.e. #Sym( α V AR , Q

V AR ) = 1 (see Section B.11 in [START_REF] Mariadassou | Consistency and asymptotic normality of stochastic block models estimators from sampled data[END_REF] for a proof of this result). Then, Proposition 1 implies that

On the other hand, we bound the term

by combining the two following propositions from [START_REF] Mariadassou | Consistency and asymptotic normality of stochastic block models estimators from sampled data[END_REF] :

Proposition 2 (Proposition 6.8 in [START_REF] Mariadassou | Consistency and asymptotic normality of stochastic block models estimators from sampled data[END_REF]). Let (t n ) n∈N be a positive sequence such that t n → 0 and pnt n / log(n) → +∞. Then, on an event of probability going to 1 and for n large enough,

where

Proposition 3 (Proposition 6.10 in [START_REF] Mariadassou | Consistency and asymptotic normality of stochastic block models estimators from sampled data[END_REF]). There exists a positive constant C such that

Combining Propositions 2 and 3, we find that on a event of probability going to 1,

. Now, we use the definition of the variational estimator and Equation ( 17), and find that

Thus,

Combining Equations ( 18), ( 19) and ( 20), we find that

Dividing both sides by l

, we find that

which proves Equation [START_REF] Chen | Network cross-validation for determining the number of communities in network data[END_REF].

Proof of Equation (12)

By definition of J X ,

).

Equation [START_REF] Gao | A general framework for Bayes structured linear models[END_REF] implies that

Now, using Pinsker's inequality, we see that

We use Equation [START_REF] Chen | Network cross-validation for determining the number of communities in network data[END_REF] and the definition of z (V AR) to conclude the proof of Equation [START_REF] Daudin | A mixture model for random graph[END_REF].

Proof of Equation [START_REF] Dhara | Spectral recovery of binary censored block models[END_REF] functions l (A; α, Q) and l (A, z; α, Q) provide lower and upper bounds on the variational objective function J (A; τ, α, Q) : for any parameter (α, Q) and any label function

To prove Proposition 3, we first show that P •|A, α V ar , Q

V ar , i.e. the posterior distribution of z at the variational estimator ( α V ar , Q

V ar

), concentrates around δ z , the dirac distribution at the label function

Then, we show that it implies the concentration of the estimator z V ar :

Together ( 25) and ( 26) imply P z V ar ∼ z * |A = 1 -o p (1). Since the random variable P z V ar ∼ z * |A is bounded, Equation ( 26) also implies that it converges to 1 in expectation. Finally, we show that with probability going to one, the maximum likelihood estimator of the label function is equal to the true label function (up to permutation):

which concludes the proof of the first part of Theorem 3.

To prove the second part of Theorem 3, we show that the maximum likelihood estimator studied in Proposition 3 is equal to the restricted maximum estimator studied in Theorem 1. More precisely, define

. Theorem 1 implies that for some absolute constant C > 0,

where the restricted maximum likelihood estimator Θ r is defined as

One the other hand, Proposition 3 implies that with probability going to one, the variational estimator of the probabilities of connections Θ V AR is equal to the maximum likelihood estimator Θ given by

We show that

which concludes the proof of Theorem 3.

Proof of Equation (25)

The proof of Equation ( 25) relies on results proven in [START_REF] Bickel | Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels[END_REF], which we recall for the sake of completeness. For any two parameters (α, Q) and (α , Q ) in Q, we say that (α , Q ) ∈ S α,Q if there exists a permutation σ of {1, ..., k} such that for any (a, b) ∈ {1, ..., k} 2 , Q σ(a),σ(b) = Q a,b and α σ(a) = α a .

Theorem 5 (Theorem 1 in [START_REF] Bickel | Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels[END_REF]). Let (z * , A) be generated from a stochastic block model with parameters (α * , Q * ) ∈ Q such that Q 0 has no identical columns and ρ n log(n)/n. Then, for any

Proposition 7 (Lemma 3 in [START_REF] Bickel | Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels[END_REF]). Let (z * , A) be generated from a stochastic block model with parameters (α * , Q * ) ∈ Q such that Q 0 has no identical columns and ρ n log(n)/n. Then,

. By definition of l and l ,

Using Proposition 7, we have that

Moreover, we note that max

by the definition of z . Then, applying Theorem 5, we get that

Combining Equations ( 29), [START_REF] Kossinets | Effects of missing data in social networks[END_REF] and [START_REF] Kshirsagar | Techniques to cope with missing data in host-pathogen protein interaction prediction[END_REF], we obtain that

Thus,

On the one hand, using Equation [START_REF] Hastie | Matrix completion and low-rank svd via fast alternating least squares[END_REF] and the definition of ( τ V AR , α V AR , Q

V AR

), we find that

Also, by the definition of l and l , we have that l A, z ; α V AR , Q

Now, we can conclude the proof of Equation ( 25) by noticing that

and using Equation [START_REF] Longepierre | Consistency of the maximum likelihood and variational estimators in a dynamic stochastic block model[END_REF].

Proof of Equation ( 26) By the definition of J (A; τ, α, Q), we have that

, so

. Now, using Pinsker's inequality, we see that

We use Equation [START_REF] Hofman | Bayesian approach to network modularity[END_REF] and the definition of z (V AR) to conclude the proof of Equation [START_REF] Holland | Stochastic blockmodels: First steps[END_REF].

Proof of Equation ( 27) Equation ( 27) is proven in [START_REF] Bickel | A nonparametric view of network models and newman-girvan and other modularities[END_REF]. In this work, the authors define the profile likelihood modularity Q LM (A, z) of a label function z ∈ Z n,k as For ẑLM = arg max z∈Z n,k Q LM (A, z), the authors of [START_REF] Bickel | A nonparametric view of network models and newman-girvan and other modularities[END_REF] prove that under the assumptions of Proposition 3, with probability going to 1, ẑLM ∼ z * . Since maximizing Q LM (A, z) is equivalent to maximizing max Q L (A; Q, z), this implies that z ∼ z * with probability going to 1.