Les réseaux complexes sont des ensembles constitués d’un grand nombre d’entités interconnectées par des liens. Ils sont modélisés par des graphes dans lesquels les noeuds représentent les entités et les arêtes entre les noeuds représentent les liens entre ces entités. Ces graphes se caractérisent par un très grand nombre de sommets et une très faible densité de liens. Les réseaux sociaux sont des exemples de réseaux complexes où les entités sont des individus et les liens sont les relations (d’amitié, d’échange de messages) entre ces individus.L’analyse des réseaux complexes est généralement basée sur l’exploration locale du graphe sous-jacent : après avoir traité un nœud u, les prochains noeuds auxquels l’application fait référence appartiennent au voisinage de u. Étant donné que le graphe sous-jacent est habituellement non structuré, les séquences d’accès aux données en mémoire tendent à avoir une faible localité lorsque qu’on utilise par exemple le stockage de Yale qui est l’un des meilleurs connus. En plus, dans les applications basées sur l’analyse des réseaux le nombre de calculs requis pour chaque noeud peut être très variable, ce qui, dans les mises en œuvre parallèles (multithreadées), se traduit par un déséquilibre de charges entre les threads.Le travail réalisé dans cette thèse était lié au développement d’applications d’analyse des réseaux sociaux, qui soient à la fois faciles à écrire et efficaces. A cet effet, deux pistes ont été explorées: a)L’exploitation de la structure en communautés pour définir des techniques de stockage qui réduisent les défauts de cache lors de l’analyse des réseaux sociaux; b)La prise en compte de l’hétérogénéité des degrés des noeuds pour optimiser la mise en oeuvre parallèle.La première contribution de cette thèse met en évidence l'exploitation de la structure en communautés des réseaux complexes pour la conception des algorithmes de numérotation des graphes (NumBaCo, CN-order) permettant la réduction des défauts de cache des applications tournant dans ces graphes.Les résultats expérimentaux en mode séquentiel sur plusieurs architectures (comme Numa4) ont montré que les défauts de cache et ensuite le temps d'exécution étaient effectivement réduits; et que CN-order se sert bien des avantages des autres heuristiques de numérotation (Gorder, Rabbit, NumBaCo) pour produire les meilleurs résultats.La deuxième contribution de cette thèse a considéré le cas des applications multi-threadées. Dans ce cas, la réduction des défauts de cache n'est pas suffisante pour assurer la diminution du temps d'exécution; l'équilibre des charges entre les threads doit être assuré pour éviter que certains threads prennent du retard et ralentissent ainsi toute l'application. Dans ce sens, nous nous sommes servis de la propriéte de l'hétérogénéité des dégrés des noeuds pour développer l'heuristique Deg-scheduling. Les résultats expérimentaux avec plusieurs threads sur l'architecture Numa4 montrent que Deg-scheduling combiné aux heuristiques de numérotation permet d'obtenir de meilleur résultats.La dernière contribution de cette thèse porte sur l'intégration des deux catégories d'heuristiques développées dans les DSLs parallèles d'analyse des graphes. Par exemple, avec le DSL Green-Marl, les performances sont améliorées à la fois grâce aux heuristiques de numérotation et grâce aux heuristiques d’ordonnancement (temps réduit de 35% grâce aux heuristiques). Mais avec le DSL Galois, les performances sont améliorées uniquement grâce aux heuristiques de numérotation (réduction de 48%). / A complex network is a set of entities in a relationship, modeled by a graph where nodes represent entities and edges between nodes represent relationships. Graph algorithms have inherent characteristics, including data-driven computations and poor locality. These characteristics expose graph algorithms to several challenges, because most well studied (parallel) abstractions and implementation are not suitable for them. The main question in this thesis is how to develop graph analysis applications that are both --easy to write (implementation challenge), -- and efficient (performance challenge)? We answer this question with parallelism (parallel DSLs) and also with knowledge that we have on complex networks (complex networks properties such as community structure and heterogeneity of node degree).The first contribution of this thesis shows the exploitation of community structure in order to design community-aware graph ordering for cache misses reduction. We proposed NumBaCo and compared it with Gorder and Rabbit (which appeared in the literature at the same period NumBaCo was proposed). This comparison allowed to design Cn-order, another heuristic that combines advantages of the three algorithms (Gorder, Rabbit and NumBaCo) to solve the problem of complex-network ordering for cache misses reduction. Experimental results with one thread on Core2, Numa4 and Numa24 (with Pagerank and livejournal for example) showed that Cn-order uses well the advantages of the other orders and outperforms them.The second contribution of this thesis considered the case of multiple threads applications. In that case, cache misses reduction was not sufficient to ensure execution time reduction; one should also take into account load balancing among threads. In that way, heterogeneity of node degree was used in order to design Deg-scheduling, a heuristic to solve degree-aware scheduling problem. Deg-scheduling was combined to Cn-order, NumBaCo, Rabbit, and Gorder to form respectively Comm-deg-scheduling, Numb-deg-scheduling, Rab-deg-scheduling and Gor-deg-scheduling. Experimental results with many threads on Numa4 showed that Degree-aware scheduling heuristics (Comm-deg-scheduling, Numb-deg-scheduling, Rab-deg-scheduling and Gor-deg-scheduling) outperform their homologous graph ordering heuristics (Cn-order, NumBaCo, Rabbit, and Gorder) when they are compared two by two.The last contribution was the integration of graph ordering heuristics and degree-aware scheduling heuristics in graph DSLs and particularly Galois and Green-Marl DSLs. We showed that with Green-Marl, performances are increased by both graph ordering heuristics and degree-aware scheduling heuristics (time was reduced by 35% due to heuristics). But with Galois, performances are increased only with graph ordering heuristics (time was reduced by 48% due to heuristics).In perspective, instead of using complex networks properties to design heuristics, one can imagine to use machine learning. Another perspective concerns the theoretical aspect of this thesis. We showed that graph ordering for cache misses reduction and degree-aware scheduling for load balancing problems are NP-complete. We provided heuristics to solve them. But we didn't show how far these heuristics are to the optimal solutions. It is good to know it in the future.

Le concept de réseau offre un modèle de représentation pour une grande variété d'objets et de systèmes, aussi bien naturels que sociaux, dans lesquels un ensemble d'entités homogènes ou hétérogènes interagissent entre elles. Il est aujourd'hui employé couramment pour désigner divers types de structures relationnelles. Pourtant, si chacun a une idée plus ou moins précise de ce qu'est un réseau, nous ignorons encore souvent les implications qu'ont ces structures dans de nombreux phénomènes du monde qui nous entoure. C'est par exemple le cas de processus tels que la diffusion d'une rumeur, la transmission d'une maladie, ou même l'émergence de sujets d'intérêt commun à un groupe d'individus, dans lesquels les relations que maintiennent les individus entre eux et leur nature s'avèrent souvent être les principaux facteurs déterminants l'évolution du phénomène. C'est ainsi que l'étude des réseaux est devenue l'un des domaines émergents du 21e siècle appelé la "Science des réseaux". Dans ce mémoire, nous abordons trois problèmes de la science des réseaux: le problème de la diffusion dans les réseaux sociaux, où nous nous sommes intéressés plus particulièrement à l'impact de la dynamique du réseau sur le processus de diffusion, le problème de l'analyse des réseaux sociaux, dans lequel nous avons proposé une solution pour tirer parti de l'ensemble des informations disponibles en combinant les informations sur la structure du réseau et les attributs des noeuds et le problème central de la collecte de données sociales, où nous nous sommes intéressés au cas particulier de la collecte de données en milieux sauvages / The concept of network provides a model for representing a wide variety of objects and systems, both natural and social, in which a set of homogeneous or heterogeneous entities interact. It is now widely used to describe various kinds of relational structures. However, if everyone has an idea of the concept of network, we often ignore the implications that these structures have in real world phenomena. This is for example the case of processes such as the spread of a rumor, the disease transmission, or even the emergence of subjects of common interest for a group of individuals, in which the relations maintained between individuals, and their nature, often prove to be the main factors determining the evolution of the phenomenon. This is the reason why the study of networks has become one of the emerging areas in the 21st century called the "Science of networks." ln this thesis, we address three issues of the domain of the science of networks: the problem of diffusion in social networks, where we have addressed more particularly the impact of the network dynamics on the diffusion process, the problem of the analysis of social networks, in which we have proposed a solution to take full advantage of all information available on the network by combining information on both structure and node attributes and the central problem of the social data collection, for which we have focused on the particular case of the data collection in a wild environment.