Search

Social Internet of Things (SIoT) is a new standard resulting from the integration of the Internet of Things (IoT) and social networking. IoT is a visionary, one-paradigm, whereas social networks are platforms where voluminous collaborations between humans exist. The SIoT is defined as a social network of objects that are not only smarter but also socially conscious. Fundamental requirements of both IoT and SIoT networks include efficient service search and the discovery of object mechanisms. Therefore, our paper proposes a simple model for social networks to discover the object or services by using a small-world network. Our proposed model comprised a set of objects, and where each object is looking for a service. The service search is initiated in different hops by an object using a service query message to the nearest object. If the requested object is identified immediately or at the first hop, a permanent link is established between the service requester and the service provider otherwise the search process is repeated until the service is discovered. In this study, we integrate the SIoT with the small world concept for the building of our model. Our proposed model guarantees that the object containing the information is in a bounded path length and is treatable owing to the structure of small-world networks. The process of search is efficient because it is initiated only when an object asks for another object or service. Our intention here is to increase the navigability of the network. We carefully performed numerical analyses for our model and presented the simulation results based on efficiencies such as average path length, clustering coefficient, service execution time, and the giant component. After conducting various experiments, we conclude that our proposed model is efficient and reflects the real network structures of small-world networks, therefore, it can be suitable for social networks.

Mental workload has been widely estimated based on electroencephalography (EEG) in the frequency domain. However, simple frequency features are not entirely accurate indicators of the cognitive load because surface EEG signals are weak, nonstationary and randomness. We hypothesize that graph methods, which analyse the relationship between each point and other points of the EEG signals, may provide a more precise identification of the mental load. To investigate this hypothesis, we aim to identify the optimum graph features from 14 channel EEG recordings (sampling rate = 128 Hz) in order to detect the high cognitive load related to multitasking. Three graph features: mean degree $\overline {d}$ , clustering coefficient $\overline {c}$ , and degree distribution $p(k)$ , are extracted from 48 subjects EEG records. Each experimental subject conducts two tasks: without tasks and with a simultaneous capacity task, respectively. After the experiment is completed, the feeling of the subject with the cognitive load tags in three types: low load, medium load, and heavy load. The optimal features of these three levels of the subject sensation and two types of cognitive load in different tasks are selected on the basis of statistical analysis. Then all graph features are forwarded into a support vector machine (SVM) and a decision tree to conduct objective scoring classification and a three subjective rating classification, respectively. Based on the present results,channels O2, T8, FC6, F8, and AF4 are considered optimal for a more efficiently estimation of the cognitive load. $\overline {c}$ associated with F8 and T8 during low cognitive load is significantly lower than those associated with high cognitive load (p < 0.001). Using three graph features, the accuracy of identifying two types of mental load is 89.6%. Current findings suggest that the mental workload associated with multi-tasks can be accurately assessed using the graph approaches to EEG data.

Research on graph classification tasks based on graph neural networks has attracted wide attention. The graphs to be classified may have various graph sizes (i.e., different numbers of nodes and edges) and have various graph properties (e.g., average node degree, diameter, and clustering coefficient). The diverse property of graphs has imposed significant challenges on existing graph learning techniques since diverse graphs have different best-fit hyperparameters. Consequently, it is unreasonable to learn graph representation from a set of diverse graphs by a unified graph neural network. Inspired by this, we design an end-to-end Multiplex Graph Neural Network (MxGNN) that learns graph representations with multiple GNNs, and combines them with a learnable method. The main challenge lies with the combination of multiple representation results. Our new findings show that the a priori graph properties do have an effect on the quality of representation learning, which can be used to guide the learning. Our experiments on graph classification with multiple data sets show that the performance of MxGNN is better than the existing graph representation learning methods.

Graph embedding aims to represent node structural as well as attribute information into a low-dimensional vector space so that some downstream application tasks such as node classification, link prediction, community detection, and recommendation can be easily performed by using simple machine learning algorithms. The graph convolutional network is a neural network framework for machine learning on graphs. Because of its powerful ability to model graph data, it is currently the best choice for graph embedding. However, most existing graph convolutional network-based embedding algorithms not only ignore the data distribution of the latent codes but also lose the high-order proximity between nodes in a graph, leading to inferior embedding. To mitigate this problem, we investigate how to enforce latent codes to match a prior distribution, and we introduce random walk to preserve high-order proximity in a graph. In this paper, we propose a novel graph embedding framework, Adversarial and Random Walk Regularized Graph Embedding (ARWR-GE), which jointly preserves structural and attribute information. ARWR-GE adopts an adversarial training scheme to enforce the latent codes to match a prior distribution, and by employing the skip-gram model, nodes in a random walk sequence are closer in the latent space. We evaluate our proposed framework by using three real-world datasets on link prediction, graph clustering, and visualization tasks. The results demonstrate that our framework achieves better performance than state-of-the-art graph embedding algorithms.

This paper studies the relationship between the clustering coefficient of nodes and the community structure of the network. Communities in a network are regarded as node-induced subgraphs of the network in this study. We define the border of a subgraph and the node network density of a node and present a formal definition of community from the view of examining the subgraph borders. Afterward, we analyze the relationship between the change in node clustering coefficients and in node network density and set the rule for identifying inter community edges. Finally, we propose a novel divisive algorithm for community detection by iteratively removing inter community edges. The time complexity of our algorithm is O(Nd2) , which increases linearly with the network size. Experiments on both synthetic and real-world networks show that introducing node clustering coefficients into the divisive algorithm can greatly improve the time efficiency of the algorithm while guaranteeing the accuracy of community detection.

Traditional abnormal trajectory detection algorithms mainly involve the measurement of a single feature; however, the influence of other features on abnormal trajectory is ignored, resulting in the inability to fully discover the abnormal trajectory in the trajectory database. To overcome this limitation, we propose an abnormal trajectory detection method – called $TADSS$ – to find the hidden abnormal trajectory by using a comprehensive measurement. Firstly, we employ three kernel functions to measure the time, velocity and position feature values of trajectory data, where the kernel functions extract semantic feature of the position, time feature of trajectory, and velocity feature of object motion from each trajectory data. Secondly, we propose a feature fusion strategy to measure the similarity of trajectory data, where we assign weights to the above kernel functions and then use a linear combination approach to fuse the weighted kernel functions. Thirdly, we build a trajectory feature graph by using the above fused kernel functions, and then divide the trajectory feature graph into a plurality of subgraphs by using a conventional graph clustering technique. Last, we propose a sparse subgraph method to detect abnormal trajectory, where a novel weight coefficient concept is used to distinguish sparse subgraph. Experimental results driven by both the vehicle trajectory data of Shanghai city and the Atlantic hurricane data demonstrate the performance of our $TADSS$ .

Indexación: Scopus. 'Mercado Público' is a Chilean electronic platform used for purchasing processes by Chilean public organizations for the last two decades. The main aim of this study is to characterize the Chilean public procurement ecosystem by using social network analysis to detect the main communities of suppliers based on who awarded the tenders. To do this, we use a methodology that first represents the bidder-supplier relationship as a bipartite graph using purchase order information. Then we project the bipartite graph onto a monopartite graph of suppliers. We end by detecting the main supplier communities using a modularity algorithm. When we applied this methodology to the large tender segment in the Chilean public procurement market over a period of four years, we successfully detected the five largest communities and the micro and small companies which had the greatest rate of participation over time. https://ieeexplore.ieee.org/document/9149588

Based on relevant complex network theory, this paper analyzes the characterization parameters of traffic network complexity, such as the causes of traffic congestion and evacuation models. From the perspective of the traffic capacity of traffic network nodes, combined with the transit time of each road, model is proposed for selecting the weights of congestion evacuation nodes. According to the evacuation target, combined with characteristic parameters, such as node degree, node strength, clustering coefficient and closeness, the grey system evaluation method and the analytic hierarchy process (AHP)are combined. Based on the grey relational analysis model, a model is established for determining the priority connectivity evaluation value of each node. The complex characteristics of the actual traffic network in the Chaoyang District of Changchun City are analyzed, then the selection weights of each node of the traffic network are obtained. Having defined the distance between complex network nodes, a congestion evacuation path selection model is proposed, and an evacuation path scheme is given for specified start and end points. Published version

Real-world networks contain many cliques since they are usually built from them. The analysis that goes behind the cliques is fundamental because it discovers the real structure of the network. This article proposed new high-order closed trail clustering and closure coefficients for evaluation of the network structure. These coefficients are able to describe the inner structure of the network concerning its randomized or organized behavior. Moreover, the coefficients can cluster networks with similar structures together. The experiments show that the coefficients are useful in both the local and global context. Web of Science 8 101152 101145

Identifying geochemical patterns from backgrounds and generating associated mineralization remains challenging due to the complex structure of mineral deposits. To learn how to identify geochemical anomalies that are spatially associated with mineralization, we need in-depth knowledge of the dependence process. Quantitative association rules (QARs) are applied to discover remarkable relations and dependencies between attributes in a dataset, but it is difficult to generate relationships from geochemical data. In previous studies, no methodology to find association rules is proposed to deal with geochemical data problem, and the classical methods designed for Boolean and nominal attributes require previous discretization, which makes the whole process limited in processing complex data. In this paper, we proposed a hybrid method of graph clustering and quantitative association rules (GCQAR) as a new way of identifying significant geochemical patterns. Graph Clustering (GC) is used as partitioning paradigm because of its ability to handle large-scale datasets. The GC is based on modularity to effectively generate the groups of the graph, to avoid the over-partitioning, and to cover all the rules. In each partition, a set of geochemical quantitative association rules is produced. The results obtained in the experimental study performed on data collected in the field of Xiaoshan, Henan province, China. Our GCQAR has significant benefits in terms of recognition geochemical patterns compared to the traditional methods used in the field of geochemistry.

Graph theory analysis, a mathematical approach, has been applied in brain connectivity studies to explore the organization of network patterns. The computation of graph theory metrics enables the characterization of the stationary behavior of electroencephalogram (EEG) signals that cannot be explained by simple linear methods. The main purpose of this study was to systematically review the graph theory applications for mapping the functional connectivity of the EEG data in neuroergonomics. Moreover, this article proposes a pipeline for constructing an unweighted functional brain network from EEG data using both source and sensor methods. Out of 57 articles, our results show that graph theory metrics used to characterize EEG data have attracted increasing attention since 2006, with the highest frequency of publications in 2018. Most studies have focused on cognitive tasks in comparison with motor tasks. The mean phase coherence method, based on the “phase-locking value,” was the most frequently used functional estimation technique in the reviewed studies. Furthermore, the unweighted functional brain network has received substantially more attention in the literature than the weighted network. The global clustering coefficient and characteristic path length were the most prevalent metrics for differentiating between global integration and local segregation, and the small-worldness property emerged as a compelling metric for the characterization of information processing. This review provides insight into the use of graph theory metrics to model functional brain connectivity in the context of neuroergonomics research.

Graph clustering is a fundamental task in data analysis and has attracted considerable attention in recommendation systems, mapping knowledge domain, and biological science. Because graph convolution is very effective in combining the feature information and topology information of graph data, some graph clustering methods based on graph convolution have achieved superior performance. However, current methods lack the consideration of structured information and the process of graph convolution. Specifically, most of existing methods ignore the implicit interaction between topology information and feature information, and the stacking of a small number of graph convolutional layers leads to insufficient learning of complex information. Inspired by graph convolutional network and auto-encoder, we propose a deep graph structured clustering network that applies a deep clustering method to graph structured data processing. Deep graph convolution is employed in the backbone network, and evaluates the result of each iteration with node feature and topology information. In order to optimize the network without supervision, a triple self-supervised module is designed to help update parameters for overall network. In our model, we exploit all information of the graph structured data and perform self-supervised learning. Furthermore, improved graph convolution layers significantly alleviate the problem of clustering performance degradation caused by over-smoothing. Our model is designed to perform on representative and indirect graph datasets, and experimental results demonstrate that our model achieves superior performance over state-of-the-art models.

The previous research on the controllability of complex networks is qualitative issue which can only identify whether the network is controllable or not, and it is difficult to assess the controlled ability of network. In this paper, a quantitative measurement index of network controllability is introduced. And the index is used to study the controllability of the IEEE power network system. The relationship between controllability and network parameters (including the average degree, the clustering coefficient, the average path length) of power network is analyzed by comparing with the ER random network, WS small world network, BA scale-free network and CM network. The results show that the power networks have a small average path length and a higher clustering coefficient, which belong to the small world network. And, the controllability of power networks is larger than the corresponding model networks, indicating that power networks are relatively easier to be controlled.

Opinion dynamics is the basic research content of social network research. Traditional opinion dynamics models focus on the heterogeneity of regular users, but ignore the heterogeneity of media users in social networks. Compared to regular users, media users have the characteristics of releasing more information and having greater influence, and their opinions are not easily affected by regular users. Aiming at the characteristics of information transmission with the participation of media users, we propose an opinion dynamics model to reproduce a realistic process of opinion interaction between regular users and media users and between regular users, respectively. The time variable is also incorporated into the probability of opinion adoption to make sure the opinion interaction model has timeliness. The simulation experiments on models of four typical complex network structures have shown that the characteristic of large average path length in a regular network will lead to the media opinion spreading slowly with a small scope, and a low individual opinion interaction frequency. On the other hand, the characteristics of strong heterogeneity and many center users in a scale-free network lead to media opinion spreading fast with a big scope. Moreover, the opinion adoption probability has a great influence on the average opinion value of the final state in four networks, while the bounded trust threshold has a great influence on opinion evolution in regular networks and scale-free networks. Furthermore, the media location selection approach based on the node betweenness results in opinion influence transmission with high speed and large range compared with the approaches based on node degree and clustering coefficient.

Although automatic fuzzy clustering framework (AFCF) based on improved density peak clustering is able to achieve automatic and efficient image segmentation, the framework suffers from two problems. The first one is that the adaptive morphological reconstruction (AMR) employed by the AFCF is easily influenced by the initial structuring element. The second one is that the improved density peak clustering using a density balance strategy is complex for finding potential clustering centers. To address these two problems, we propose a fast and automatic image segmentation algorithm using superpixel-based graph clustering (FAS-SGC). The proposed algorithm has two major contributions. First, the AMR based on regional minimum removal (AMR-RMR) is presented to improve the superpixel result generated by the AMR. The binary morphological reconstruction is performed on a regional minimum image, which overcomes the problem that the initial structuring element of the AMR is chosen empirically, since the geometrical information of images is effectively explored and utilized. Second, we use an eigenvalue gradient clustering (EGC) instead of improved density peak (DP) algorithms to obtain potential clustering centers, since the EGC is faster and requires fewer parameters than the DP algorithm. Experiments show that the proposed algorithm is able to achieve automatic image segmentation, providing better segmentation results while requiring less execution time than other state-of-the-art algorithms.

The abundance and real-time availability of Twitter data have proved beneficial in detecting events in various domains such as emergency situations, crime detection, public health, place recommendations, etc. Nevertheless, two critical challenges occur while detecting events using social media data. First, the uncertainty in capturing the contextual relationship among tweets, which is the result of the limited availability of the contextual information due to the small length of tweets. Second, the high computation cost required in event detection due to massive data processing. Earlier research works, addressing these challenges, have tried to capture the contextual information by using the dense vector representations of texts leveraging deep neural word embedding generation models such as Word2Vec and GloVe. However, these models are trained on the Euclidean vector space which fails to amalgamate the directional information of the vectors with the semantic information in text, incurring high computational costs. To target both the problems simultaneously, we propose modeling Twitter data as a graph-of-sentences which retains the contextual relationships while maintaining lower computational cost. The proposed model captures contextual information using JoSE, a spherical vector representation leveraging the word-word and word-paragraph semantic co-occurrence statistics in a spherical generative model. Furthermore, the framework uses the weighted-graph model to capture all the relationships among the Twitter data efficiently. The graph is further pruned with the help of the graph component filtering approach. The graph clustering model, employed to detect the events, leverages the edge weights and the partial-k clustering approach maintaining low computation costs. The experimentation on the annotated benchmark Twitter data set and the real-world datasets show improved run-time performance up to 30% while maintaining the qualitative performance (F1-score) comparable to the state-of-the-art models.

Unmanned aerial vehicles (UAVs) also known as drones are increasingly populating our skies. This represents a relevant issue both for the legislator and the researcher. While the regulation plans often assume precautionary approaches, stating restrictive conditions of use for the sake of public safety, the applied research is exploring novel strategies to develop autonomous vehicles endowed with trusty operating mechanisms. The challenge is to let drones overflying even populated areas while keeping a steady control of the situation on the ground, thus enabling the possibility of safe landing with no harm for people. This can be done employing on-board cameras and embedded GPUs which allow for the execution in real-time of computer vision applications. In this paper, we introduce a crowd detection method for drone safe landing. The pivotal points of our proposal are related to the computational limitations imposed by the currently available hardware resources of UAVs. In this sense, our method is based on the light-weight scheme of a fully-convolutional neural network which conjugates nimble computations and effectiveness. We propose a two-loss model where a classification task (oriented to distinguish between crowded/non-crowded scenes) is supported by a regression task (aimed at better focusing the agglomeration tendency of the persons). This latter job is realized by resorting to the construction of a spatial graph for each analysed image and to the evaluation of the corresponding clustering coefficient. As a further element, our model is endowed with the capability to produce class activation heatmaps which contribute to the semantic enrichment of the flight maps. We tested our model on a large dataset of aerial images and we observed how it compares favorably with other approaches proposed in literature.

As a crucial travel mode, taxi plays a significant role in residents' daily travel. Uncovering taxi traffic demand has become a hotspot in transport studies. Previous researchers pay more attention to the statistical characteristics of taxi trips, while few studies focus on the dynamic features in different periods of a day. In this article, we study the taxi travel demand by constructing dynamic networks based on taxi trajectory data. In addition, relationship between travel intensity and point of interest (POI) in Xiamen, China is discussed. Firstly, the study area is divided by 1km × 1km uniform cells. The pick-up and drop-off activities of passengers are recorded for each cell. Secondly, the networks are constructed by regarding each cell as a node and regarding taxi trips from a cell to another cell as an edge. On this basis, we divide a day into 12 periods by two hours and construct the networks for different periods. Finally, correlation between travel intensity and POI intensity is detected with regression analysis. Results show that the taxi trip networks have large clustering coefficient and small shortest path length, which indicates they are `small world' networks. Moreover, the taxi trip networks are disassortative networks that hotspot areas tend to connect with the common areas. Furthermore, the taxi trip length in a day follows a lognormal distribution and the peak hour of taxi trip appears around midnight. Finally, a cubic polynomial curve could fit the relationship between travel intensity and POI intensity. Our findings provide a new insight for understanding the traffic demand of taxi.

Influential nodes identification in complex networks is vital for understanding and controlling the propagation process in complex networks. Some existing centrality measures ignore the impacts of neighbor node. It is well-known that degree is a famous centrality measure for influential nodes identification, and the contributions of neighbors also should be taken into consideration. Furthermore, topological connections among neighbors will affect nodes' spreading ability, that is, the denser the connections among neighbors, the greater the chance of infection. In this paper, we propose a novel centrality, called DCC, to identify influential nodes by comprehensively considering degree and clustering coefficient as well as neighbors. The weights of degree and clustering coefficient are calculated by entropy technology. To verify the feasibility and effectiveness of DCC, the comparisons between DCC and other centrality measures in four aspects are conducted based on four real networks. The experimental results demonstrate that DCC is more effective in identifying influential nodes.

There may exist many high-energy particles in spacecraft, so the FPGA circuits design needs corresponding sensitivity analysis and security reinforcement of anti-SEE (Single-event effects). However, it may be impractical to perform such measures to all modules of FGPA circuits due to limited resources. To identify the key modules which have a vital impact on the design and operation of FPGA circuits in spacecraft, this paper presents a novel scheme based on complex network for modeling the modules considering both the circuit functional structure and signal interaction relationship between modules. First, complex networks like MSN (Module Structure Network) and SFN (Signal Flow Network) are established to identify modules by treating each module as a node, and indicators including degree centrality (DC), betweenness centrality (BC), clustering coefficient (CC), etc., are calculated. Then, an entropy-weight method (EWM) is utilized to calculate the indicators comprehensively for identifying key modules. Next, network efficiency and sensitivity analysis are performed for failure modes. Finally, a case study is carried out, demonstrating the effectiveness of the proposed scheme for the key module identification. This work provides useful technical support for engineers in spacecraft FPGA circuits design and performance enhancement.

As the continuous development of mobile social networks, the structure of the mobile social network increasingly becomes complex. It not only speeds up information transmission between people but also expands the scope of information exchange, which has become an essential and important social media in people's social life. How to effectively identify and classify these online communities has important practical significance for the study of social networks. Correctly detecting the community structure of mobile social networks can not only improve the accuracy of friend recommendation, link prediction, service user positioning, product marketing, and other aspects but also provide an important basis for the monitoring of online public opinion. But the traditional social network cluster method based on the trust degree mainly calculates the user trust by analyzing the interactive feedback information between users. This method cannot effectively solve the “cold start” problem in the trust calculation process, that is, for the new network node, the trust value of this node cannot be accurately measured due to the lack of interaction with other nodes. Focusing on this problem, we propose a Gaussian pigeon-oriented graph clustering algorithm for social networks' cluster in this paper. A graph model is first built. Then, an efficient K-medoid algorithm is utilized to search the user center in all groups. The Gaussian pigeon algorithm is used to search the similarity between each user and the central user. Users that meet the similarity threshold are divided into the same user group. Finally, the simulation results show that the proposed method has better cluster effect than other state-of-the-art social networks' clustering approaches.

Graph clustering is to partition a large graph into several subgraphs according to the topological structure and node characteristics of the graph. It can discover the community structures of complex networks and thus help researchers better understand the characteristics and structures of complex networks. This paper first proposes the concepts of direct attraction force and indirect attraction force. Then, it defines a new structural similarity, attraction-force similarity. Finally, the AF-Cluster algorithm is proposed based on the attraction-force similarity. Through the experimental analysis, we can conclude that the AF-Cluster algorithm is effective for clustering graph compared with other contrast algorithms.

Community structures are integral and independent parts in a network. Community detection plays an important role in social networks for understanding the structure and predicting user behaviors. Many algorithms have been devised for accurate and efficient community detecting, but there are few community detection algorithms using node similarity. In most real-world networks, nodes tend to create tightly knit groups characterized by a relatively high density of ties. The higher the clustering coefficient of a node, the more aggregative the neighboring nodes are. In this paper, we propose an adjacent node similarity optimization combination connectivity algorithm (ASOCCA) for accurate community detection. ASOCCA utilizes the local similarity measure based on clustering coefficient to identify the closest neighbors of each node, then obtains several sets of connected components by combining different pairs of nodes, and finally forms initial communities. In addition, the community merging strategy is applied to further optimize the community structure. To evaluate the performance of the proposed algorithm, six real-world networks and two LFR networks with diverse network size are used to compare ASOCCA with five state-of-the-art community detection algorithms. The experimental results show that ASOCCA achieves better detection accuracy than several existing algorithms.

Traffic flow information is of great importance for transport planning and related research. The conventional methods of automated data collection, such as annual average daily traffic (AADT) data, are often restricted by limited installation, while the state-of-the-art sensing technologies (e.g., GPS) only reflect some types of traffic flow (e.g., taxi and bus). Complete coverage of traffic flow is still lacking, thus demanding a rigorous estimation model. Most studies dedicated to estimating the traffic flow of the entire road network rely on single to only a few properties of the road network and the results may not be promising. This paper presents an idea of integrating five topological measures and road length to estimate traffic flow based on a multiple regression approach. An empirical study in Hong Kong has been conducted with three types of traffic datasets, namely floating car, public transport route, and AADT. Six measures, namely degree, betweenness, closeness, page rank, clustering coefficient, and road length, are used for traffic flow estimation. It is found that each measure correlates differently for the three types of traffic data. Multiple regression approach is then conducted, including multiple linear regression and random forest. The results show that a combination of various topological and geometrical measures has proved to have a better performance in estimating traffic flow than that of a single measure. This paper is especially helpful for transport planners to estimate traffic flow based on correlation available but limited flow data with road network characteristics.

The maximum $k$ -plex problem is intended to relax the clique definition with maximum cardinality. It helps people understand the structures of networks by considering them a problem of graph clustering; therefore, it is a useful model for social network analysis. In this paper, we propose a swap-based heuristic algorithm for the maximum $k$ -plex problem. Starting with a randomly selected solution, we use three types of swap operators to enlarge our current solution in different situations. The results of experiments conducted on various graphs from two benchmarks demonstrated that our proposed algorithm achieved desirable performance on specific graphs compared with other algorithms.

We propose a novel mechanism to generate a family of deterministic small-world and scale-free networks by inserting new nodes into old nodes. These models can characterize the distinguishing properties of many real-world networks because this novel class of networks incorporates some key properties characterizing a majority of real-world networked systems, namely a high clustering coefficient and a short characteristic path length. We also obtain some accurate results for their properties, including degree distribution, clustering coefficient and network diameter, exactly according to the proposed generation algorithm of the networks considered, and discuss them. The network representation approach provided here can be used to investigate the complexity of many real-world systems from the perspective of complex networks.

Refereed/Peer-reviewed Data mining task is a challenge on finding a high-quality community structure from large-scale networks. The distance dynamics model was proved to be active on regular-size network community, but it is difficult to discover the community structure effectively from the large-scale network (0.1-1 billion edges), due to the limit of machine hardware and high time complexity. In this paper, we proposed a parallel community detection algorithm based on the distance dynamics model called P-Attractor, which is capable of handling the detection problem of large networks community. Our algorithm first developed a graph partitioning method to divide large network into lots of sub-networks, yet maintaining the complete neighbor structure of the original network. Then, the traditional distance dynamics model was improved by the dynamic interaction process to simulate the distance evolution of each sub-network. Finally, we discovered the real community structure by removing all external edges after evolution process. In our extensive experiments on multiple synthetic networks and real-world networks, the results showed the effectiveness and efficiency of P-Attractor, and the execution time on 4 threads and 32 threads are around 10 and 2 h, respectively. Our proposed algorithm is potential to discover community from a billion-scale network, such as Uk-2007.

In social networks, influential spreaders are those nodes that can spread information to a large number of nodes. Identifying influential spreaders is a major challenge for applications, such as information diffusion acceleration, epidemic outbreak prevention, and effective e-commerce advertisement conduction. Existing methods consider the influence of a node’s neighbors on its spreading ability but rarely account for the topology of the neighboring nodes. Therefore, we propose a novel measure based on normalized local structure attributes, called normalized local centrality, which considers the topology of the local network around a node as well as the influence feedback of the node’s nearest neighbor nodes. First, we compute the influence of a node’s neighbors and the local clustering coefficient of them to identify nodes in cluster centers and those function as “bridge.” Then, a normalization function is designed to normalize the results to avoid adding new variable parameters. We perform experiments to identify influential spreaders in both real and computer-generated networks and compare the results on the basis of seven measures: degree, betweenness, closeness, k-shell, semi-local centrality, local structure centrality, and our proposed measure. In the susceptible–infected–recovered model, the node influence rankings obtained by our measure are most consistent with those of the benchmark, thus confirming that our method measures node influence more accurately than the other methods. Furthermore, the top-100 nodes ranked by our method lead to faster and wider spread than those ranked by the other six tested measures.

Community detection algorithms are important for determining the character statistics of complex networks. Compared with the conventional community detection algorithms, which always focus on undirected networks, our algorithm is concentrated on directed networks such as the WeChat moments relationship network and the Sina Micro-Blog follower relationship network. To address disadvantages such as lower execution efficiency and higher deviation of precision that current directed community detection algorithms always have, we propose a new approach that is based on the triangle structure of community basis and modeled on the local information transfer process to precisely detect communities in directed networks. Based on the directed vector theory in probability graphs and the dynamic information transfer gain (ITG) of vertices in directed networks, we propose the novel ITG method and the corresponding target optimal function for evaluating the partition quality in a community detection algorithm. Then, we combine ITG and the target function to create the new community detection algorithm ITG-directed weighted community clustering for directed networks. With extensive experiments using artificial network data sets and large, real-world network data sets derived from online social media, our algorithm proved to be more accurate and faster in directed networks than several traditional, well-known community detection methods, such as FastGN, order statistics local optimization method, and Infomap.

Though existing works of sign prediction have reasonable prediction performances, they suffer from the data sparseness problem, especially for the negative link prediction. Most nodes in signed social networks are connected to very limited number of other nodes, which could not provide enough knowledge for sign prediction. This paper, therefore, proposes a novel edge-dual graph preserving sign prediction model, which reconstructs the signed social network by converting the original graph into the edge-dual graph, uses Jaccard coefficient to measure the node similarity and applies support vector machine classifier to predict signs. The proposed method reconstructs the graph by converting edges of the original graph into nodes of the edge-dual graph, and creating edges for the edge-dual graph according to the connections of edges in the original graph. It is mathematically and experimentally verified that the sparseness of the signed social networks can be significantly reduced by the proposed method. Using the publicly available data sets, it is verified that the average degree of signed social networks can be 7 to 8 times enlarged by the proposed method and the sign prediction accuracy can be improved around 10% comparing with the existing works.

The issue of virtual network (VN) embedding constitutes an important aspect of network virtualization, which is considered to be one of the most crucial techniques to overcome the Internet ossification problem. The main purpose of VN embedding is to efficiently utilize the limited physical network resources to offer the supporting of virtual nodes and virtual links from the VNs. Due to the fact that the VN embedding problem is proved to be NP-hard, previous works have put forward some of heuristic algorithms to solve this VN embedding problem. However, most of the existing research works only consider the local resources of nodes, ignoring the topological attributes of its neighborhood nodes, and lead to lower resource utilization of the substrate network. To address this issue, we proposed an approach of VN embedding algorithm called VNE-DCC , which based on the node degree and the clustering coefficient information, we adopted the technique of node importance metric to rank the substrate nodes aim to select the node with the most embedding potential for every virtual node in each VN requests, and exploited the breadth-first-search algorithm to embed the virtual nodes aiming at reducing the resource utilization of substrate links so as to increase the acceptance ratio of VN requests and increase the revenues of operational providers. Extensive simulations have shown that the efficiency of our algorithm is better than the other state-of-the-art algorithms in terms of Revenue/Cost ratio and acceptance ratio.