{'fraction_non_alphanumeric': 0.034009474067776026, 'fraction_numerical': 0.013765739503623628, 'mean_word_length': 4.578139114724481, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Triangles as basis to detect communities: an application to Twitter's network

Nowadays, the interest given by the scientific community to the investigation of the data generated by social networks is increasing as much as the exponential increasing of social network data. The data structure complexity is one among the snags, which slowdown their understanding. On the other hand, community detection in social networks helps the analyzers to reveal the structure and the underlying semantic within communities. In this paper we propose an interactive visualization approach relying on our application NLCOMS, which uses synchronous and related views for graph and community visualization. Additionally, we present our algorithm for community detection in networks. A computation study is conducted on instances generated with the LFR [9]-[10] benchmark. Finally, in order to assess our approach on real-world data, we consider the data of the ANR-Info-RSN project. The latter addresses community detection in Twitter.


INTRODUCTION:
The graphs are well-known to be suitable for representing relational data in various disciplines, where the nodes and the edges, respectively, represent the entities and the relationship between these entities. For example, in sociology, graphs represent friendship in a social blog or phone-call between customers of a mobile operator, like in Blondel et al. [3] or e-mail communication like in Schlitter et al. [20]. Moreover, in biology, graphs can represent interaction between proteins, Rahman and Ngom [17]. In real-world and in common cases the edges are not binary but they are weighted. For example, the weight in the e-mail network could be the number of e-mails sent between two persons. This leads to complex and unstructured graphs, which makes the investigation tasks harder. In this context, one among the objectives in this work is to explain how the information is shared on social network. Furthermore, the objective of community detection algorithms is to reveal the semantic of the underlying network structure communities. But what is a community? A widespread definition introduces a community as a group of network's nodes having more interactions between them comparing to the other nodes. To detect such communities, in this paper we propose a community detection algorithm in weighted graphs based on the weighted maximum triangle packing to build the skeleton of communities at its first step. Thereafter, the algorithm compares the intracommunity weight and inter-community weight between groups allowing dominant communities to gain in size.
Community detection is the preliminary step to grasp the underlying semantic and the structural information in the network. It comes after the visualization issue. What is the most appropriate visualization for the detected communities and the underling information? As examples, Blondel et al. [3] use node-link for community depiction whereas word cloud is used in Yang et al. [22]. In this work, additionally to node-link representation, circle packing is used to visualize the detected communities. Also, synchronous and coordinated views help the expert user to build his/her own ideas about communities' characteristics.
The remaining part of this paper is organized as follows. In Section 2, we survey the related work to the community detection algorithms. In Section 3, we give some definitions and notations used in this paper and describe our algorithm. Experimental study of the proposed algorithm is conducted in Section 4. Section 5 introduces the case study and discusses the results relying on NLCOMS. Finally, Section 6 concludes the paper and discusses further improvements of this work.

RELATED WORK
In general, there are two major approaches for community detection in graphs. The first approach consists in computing a similarity or a distance function between each couple of nodes. Equation (1) is an example of distance function, noted as , , where , represents the positive value of the weighted edge between the ℎ and ℎ nodes and represent a constant. Then, a clustering algorithm is applied, like in Schlitter et al. [20]: The second approach relies on the graph structure. In this second approach, there are two families of algorithms. The divisive family or top-down: initially the whole graph is considered as a unique community and a divisive algorithm tries iteratively to prune the inter-community edges. As an example, we refer to the divisive algorithm of Newman and Girvan [12]. The algorithm uses the edge betweenness centrality to detect such inter-community edges, where the edge betweenness centrality metric counts the number of short-paths between all couples of nodes in which this edge belongs. The second family is the agglomerative algorithms or bottom-up: an agglomerative algorithm starts with communities, representing the number of nodes in the graph, which means that initially each node forms a community. Thereafter, the aim is to merge communities with respect to an objective function or a metric. One of the common metric used in Newman [13] and Clauset et al. [5], is the modularity , formulated by Equation (2): Where: is the community of , is the weighted graph degree of the node defined as follows: ,  Function is used to express whether the weights of edges inside communities are greater than a random edge distribution with the same properties.
The aforementioned community definition with more edges within communities than outside is still valid for the weighted context. Indeed, exchanging each weighted edge by as much edges having 1 as weight leads to a multigraph [14]. As an example of agglomerative algorithm we refer to the algorithm of Blondel et al. [3]. In the first phase of their algorithm, a merging step is achieved until a local maximum of modularity is reached; no merging can improve the modularity. In the second phase, each detected community is replaced by a meta-node. These two phases are iteratively performed until reaching a global maximum of the modularity. We refer to the papers of Leskovec et al. [11] and Lancichinetti et al. [8] for an evaluation of community detection algorithms.

OUR ALGORITHM
Before introducing our proposed algorithm for community detection, we give some definitions and notations which are necessary for a better understanding.

Definitions and Notations
Let = ( , , ) be a graph where , and denote respectively the set of nodes of size , the set of edges of size and the weights of the edges. The set of communities is ≤ . Therefore, = ∑ , ∀ ∈ . The intra-weight and the interweight , ℎ , are respectively defined as follows:  the sum of the weights of the edges within a community : = ∑ < ( , ) , ∀ , ∀ ∈  the sum of the weights of edges between two communities and ℎ : , ℎ = ∑ < ( , ) , ∀ ∈ and ∀ ∈ ℎ . Two communities and ℎ ∈ are adjacent if , ℎ ≠ 0. | | denotes the cardinality of the set . What makes a community dominant is its − ℎ or its ℎ , greater are these values, more the community is dominant. The neighbourhood degree  of triangle represents the number of triangles that overlap .
The objective of the unweighted Maximum Triangle Packing problem (MTP for short) is to find the largest collection of pairwise node-disjoint triangles (i.e., cliques of size 3) of a graph among all possible triangles =1, 2,…, , (see Abdelsadek et al. [1] for algorithms addressing the MTP problem). A weighted version of the MTP can be formulated as in Model (3), where is the decision variables' vector, is the weight of triangle l obtained by summing the weights of its edges and ∈ {0, 1} × is the node-triangle belonging matrix. We point out that there exists another formulation of the weighted MTP in Chen et al. [4].
For instance, let us consider the graph in Figure 1. In the latter a greedy solution for the weighted MTP can be obtained by selecting triangles in a decreasing order with respect to their value. Thus, we obtain the following result: {( 3 , 4 , 9 ), ( 7 , 8 , 10 ), ( 11 , 13 , 16 ), ( 12 , 17 , 18 )} = 8 + 8 + 8 + 8 = 32. The heuristic that we propose for the weighted MTP problem consists in selecting the triangles in a decreasing order with respect to the value returned by the function E defined in (4) while the disjunctive constraint is met. Figure 1: Graph example, with = for the black edges, = for the blue edges, = for the green edges and = for the red edges.
In Figure 1, {( 1 , 3 , 4 ), ( 6 , 7 , 8 ), ( 9 , 10 , 11 ), ( 13 , 14 , 16 ), ( 17 , 18 , 20 )} = 7 + 7 + 7 + 7 + 7 = 35 is returned as solution for the weighted MTP problem. This solution is optimal but is not the only optimal solution for this example. The following are the functions of the obtained solution: The motivation behind this is to select triangles as a skeleton of the communities' structure. Topologically speaking, triangles are the smallest group of interconnected nodes after edges and they are considered in various networks metrics. As an example, we refer to the global clustering coefficient of Opsahl and Panzarasa [16], the cohesion of Friggeri et al. [6] and the 3-cycle cut ratio of Klymko et al. [7] for directed networks. We think that triangles play an important role in the communities' structure. In the next developments, we will try to demonstrate this assumption.

Algorithm 1
In this section, we introduce our algorithm for community detection in weighted graphs as illustrated in Algorithm 1.
Algorithm 1 starts with communities, assigning to each community of a distinct node of . Thereby, and are computed as defined in the previous section. Then, it finds a collection of pairwise node-disjoint triangles, which are maximal, via ( ). Therefore, the endpoints of each triangle provided by ( ) have first to be considered to form a distinct community, especially for those having a large value. Then, Algorithm 1 sorts the obtained set of communities via ( ) taking into account the user's choice. The user can choose between a random, a decreasing or a decreasing order.
From there, successive steps are carried out wherein the dominant communities in get bigger. To do so, the adjacent communities are pairwise compared.
In order to avoid re-computing at each community comparison, an adjacency list of communities with the corresponding is memorised. This adjacency list is updated after each community merging. For instance, the adjacency list of the graph in Figure 1 is showed in (5 END.

COMPUTATIONAL STUDY
In this section, we conduct a computational study of Algorithm 1 on instances generated with LFR benchmark. The LFR generation scheme uses power laws for degrees and community size distributions. and are the mixing parameters which, respectively, denote the proportion between the internal and external edges for a vertex with respect to its community belonging and proportion for the weighted case. For example, a specific node will have 1 − _ edges within its community and edges out of its communities. For further details about LFR benchmark we refer to [9], and to [10] for the weighted version. The number of vertices for the generated instances are: 1000 and 5000. The community sizes are in [20,100] for 1000 nodes and in [20,500] for 5000 nodes. The average node degree is set to 20 whereas the maximum node degree is 50 for 1000 nodes and 100 for 5000 nodes. For each and ten instances are generated. Additionally, for all the instances, we set ℎ and  of Algorithm 1, respectively, to and 0.1.
The average values of the instances' characteristics with, respectively, 1000 and 5000 are presented in Table 1 and Table 2. Hereafter, we give some details on the experimental environment. All the tests are done on Intel Core i7 2.7 GHz processor and 8 GB of RAM, under Windows 8 OS. As an instance, Figure 2 an example is generated with the LFR benchmark where = 5000 and ≈ 47600 , depicted using NLCOMS (see §5.2), where node colours represent the detected communities.  .
One have to compare the ground-truth communities of the LFR benchmark and a proposed community partition. To do so with the proposed communities of Algorithm 1 we use Rand Index of [18], noted here RI expressed by formula (6).
( 1 , 2 ) = 1,1 + 0,0 1,1 + 1,0 + 0,1 + 0,0 Where 1,1 , 0,0 , 1,0 and 0,1 represent how often any couple of nodes are respectively within a community in both partitions 1 and 2 , in different communities in both partitions, within a community of 1 only (hence in different communities of 2 ) and in different communities of 1 but within a community in 2 . Closer values of RI to 1 more Algorithm 1 returns community partition, which matches the ground-truth in terms of nodes couple classification. Figure 3 shows the results obtained by Algorithm 1 for 1000 nodes. The blue dots represent the case where = whereas the red ones represent the case where = 0.5. Like in [8], the second case assumes that there is as much edges within a community as for the other communities for each node, which means that there is no topological community dominance. In the latter, a community detection algorithm devised for weighted networks has to rely only on weights (i.e., ) to identify communities. In Figure 4, the relative completion time and the modularity are presented. Figure 5 depicts the average numbers of communities detected by Algorithm 1 for the instances of Table 1.   From Figure 2 we remark that Algorithm 1 has a high RI value up to 0.5 due to triangles which have the particularity to catch the community structure as a first step, then the merging steps add the remaining vertices to each community. After this limit value (i.e., for 0.6) only one community is detected that is because there is more inter-community edges than within communities edges. We notice also that even though there is a balance between the number of inter-community edges and within community edges Algorithm 1 detects the communities relying only on the weights. Figure 6 shows the results obtained by Algorithm 1 for 5000 nodes, whereas in Figure 7, the relative completion time and the modularity are presented. Figure 8 depicts the average numbers of communities detected by Algorithm 1 for the instances of Table 2.  With these additionally instances of Table 2, Figure 6 shows that Algorithm 1 still have high RI values. However, the limit becomes equal to 0.5 which remains an acceptable limit. We point out also that Algorithm 1 performs slightly better when = 0.5 and varies, this observation holds also in Figure 2. Regarding the completion time we observe that it decreases when the number of triangles in the graph decreases.

Info-RSN project
In order to assess Algorithm 1 on real-world application, we focus on community detection in social networks and we consider the ANR Info-RSN project. In the latter, 17 millions of tweets are provided and the objectives are to provide an explanation on how the information is shared through social network (Twitter) and also to detect communities within Twitter. To fulfil this need, we have done pre-processing step on the Info-RSN database in order to get a graph model in which nodes are the persons who tweet and the edges represent either re-tweet or mention which represent, respectively, person B re-tweet the tweet of person A and person A is mentioned by person B in its tweet. Thereby, the communities induced by re-tweet edges and those induced by mention edges are complementary to investigate the sharing and propagation phenomena.

NLCOMS
An application is created to visualize and to interpret the network and the detected communities. NLCOMS, for (Node-Link and COMmunitieS), is a visual interactive application for social network analysis based on node-link representation of graphs and circle packing for the detected communities. Figure 9 gives a global sight of NLCOMS and Figure 10 shows the circle packing representation of communities detected by Algorithm 1 for the graph in Figure 2 (a). The circles size is proportional to the node graph degrees.
In Figure 9, the main view is divided into two panels labelled Node-Link and Communities. The first is the area where the node-link representation is depicted whereas the detected communities are depicted in the second panel. NLCOMS proposes other panels labelled Node-link attributes, Community detection, Data filters, Layout parameters and Stats views, in which the user can, respectively, enter the desired number of nodes or filter the graph relatively to the graph degree (i.e., we keep each connected component containing a node having a graph degree value greater than or equal to the desired user graph degree value), set the value of ℎ used in ( ) of Algorithm 1, filter the raw data of the Info-RSN database, hide labels or change the edge length and rely on some performed statistics on a selected community. NLCOMS permits to the user to decide which relationship type are represented by the edges. In this context, the edge weight ∈ represents the number of re-tweets or mentions between two persons. NLCOMS allows also tweets filtering relative to a particular tweet theme, a specific media or the date of publication. Besides, we use the visual variable of Bertin [2] on the node size, the node shape, the edge thickness and the lightness of the inner node colour which visually represent, respectively, number of followers of the person, whether the person who tweet uses twitter as reporter or as ordinary user, number of re-tweets or mentions between two persons, number of tweets of the person. Additionally, the node shape outline is coloured relative to the community node's membership. Thus, each community is coloured by a colour. Moreover, complementary and interactive bar charts help the expert user to build his/her own ideas about communities' characteristics and give some statistics about thematic and Medias source proportions within a selected community. Additionally, circular progress bar tells the expert user the tweets proportion for each community member of its tweets with respect to a selected thematic or Media source in the community representation.
NLCOMS is driven by the visual information-Seeking Shneiderman's Mantara "Overview First, Zoom and Filter, Then Details-on Demand" [21]. A global view gives to the expert user a sight of the networks structure, after a zoom on the network or on the detected communities is provided. Details appear when the expert user selects a community or a member. Effortless interactions (i.e., right and left mouse click) are utilized avoiding pointless extra cognitive load. The steps of the interactive visualization on which NLCOMS relies are presented in Figure 11.

Data sets and results
Representative samples from the Info-RSN database are considered. Table 3 illustrates the samples' characteristics of the Info-RSN database. Like for Section 4, we set ℎ and  of Algorithm 1, respectively, to and 0.1. In order to understand how the information is shared and the underlying semantic on the networks, the following set of visual tasks are considered:  What are the mains actors in the network? Have they followers?  There is atypical behaviour? Who uses Twitter as reporter?  What are the structures of the communities?  What are the mains thematics addressed and the main media source within a community?  How often a specific member tweet in a specific thematic or from a specific media source?  Is there a structural difference between networks with re-tweet edge type and mention edge type?

Data set 1 for edge re-tweet type analysis
In data set 1 the network is sparse with communities having star-like shape. From Figure 12, for the main actors we can easily distinguish their followers in the circle packing representation or in the node-link representation. The node size in the circle packing representation depicts the number of followers of a community member. Furthermore, we notice a bridge-like behaviour, which links the centroid of two star-like communities. One would say that the centric member emits the original tweet and the followers propagate them. For example, in Figure 13, if the expert user selects the pink community bar charts appear, allowing theme or media selection. The height represents the tweet percentage classified as tweets dealing with the selection theme (media) with respect to the total number of tweet within the community. The lightness bar colour depicts the proportion between community members that tweet at least one time in the selected thematic (media) and the members within the community which means darker are the bar more community members belong to it. In this context the theme 'sport' and the media 'slate.fr' are selected in Figure 13. From Figure 13 we observe that 88% of tweets in the pink community tweet are classified in the media 'slate.fr' and 14% talks about 'sport'. Additionally, the totality of the tweets of the main actor (i.e., having the most of followers depicted by the bigger circle in the pink community) is from 'slate.fr'. The combination of these representations enhances the understanding of community structure while grasping gradually and interactively the underlying information.

Data set 2 for re-tweet trends
In data set 2 the network is less messy, the communities are more distinguishable. Unlike in Figure  12, in Figure 14 the circle size is proportional to the number of tweets of each community member. NLCOMS provides circle ordering with respect to their size, which allows answering quickly to the following question; how is the most (less) active member? The thematic or media source filtering is done only on the initial tweets, which means that if a retweet occurs but the thematic of the re-tweet differs from the user expert filter, we have decided to keep the couple (tweet, re-tweet) in the network. The motivation behind this is to analyse the re-tweet trends wither the thematic or the media source change.

Figure 15: Selection of the light orange community and the 'lefigaro.fr' bar
As an example, in Figure 15, after selecting the light orange community, the histograms give the information that the dominant media in the community is 'lefigaro.fr', which reflects the initial filter. Additionally, we remark that some members tweets only from 'lefigaro.fr' whereas others have a great tweet thematic ratio. By taking these observations into account the expert user can infer the main active members on a specific media (theme).

Data set 3 for cross thematics
In Figure 16, data set 3 shows that there are some thematics, which are cross connected. For example, the thematic filter is 'war' but the main and the most tweeted thematic is 'international'.

Figure 16: Data set 3 and the user information of the centroid member
Additionally, the centroid member of the unique community is a reporter for 'france24', which is a breaking news TV channel and all other members are connected to the aforementioned reporter, suggesting that this member is the main actor in the network.

Data set 4 for edge mention type analysis
In data set 4, we investigate the mention edge type; the sample is illustrated in Figure 17. As for the previous data sets the used filter (i.e., selection of 'liberation.fr' as media) is dominant in the light blue community. An interesting observation is that the majority of the bridge-like behaviours are reporters represented by squares. Figure 18 presents completion times and the modularity of Algorithm 1 for the Info-RSN data sets. In this work, we present our algorithm for community detection in networks. Algorithm 1 uses the triangles obtained by a feasible solution of the weighted MTP problem as starting point for community detection. Then, communities are compared allowing dominating communities to gain in size. The proposed algorithm is tested on the LFR benchmark. The results show that Algorithm 1 has high RI up to = 0.5 for 1000 vertices and = 0.4 for 5000 vertices, even when = 0.5 and varies. Furthermore, we propose an interactive visualization approach relying on NLCOMS to reveal the structure and the underlying semantic within communities. Additionally, one among the objectives of this study is to understand how the information is shared on social network, especially on Twitter. To fulfill this need, we investigate real-world data of the info-RSN ANR project.
As perspectives, it is worthwhile to consider the dynamic context where the aim is not only to distinguish the interconnected communities at each time-point but also to devise an algorithm which takes advantage from the previous time-points (Nguyen et al. [15]), and the related visualization which permits to depict the evolution of communities' structure (Reda et al. [19]).