An Influence Maximization Algorithm Based on Improved K-Shell in Temporal Social Networks

Influence maximization of temporal social networks (IMT) is a problem that aims to find the most influential set of nodes in the temporal network so that their information can be the most widely spread. To solve the IMT problem, we propose an influence maximization algorithm based on an improved K-shell method, namely improved K-shell in temporal social networks (KT). The algorithm takes into account the global and local structures of temporal social networks. First, to obtain the kernel value Ks of each node, in the global scope, it layers the network according to the temporal characteristic of nodes by improving the K-shell method. Then, in the local scope, the calculation method of comprehensive degree is proposed to weigh the influence of nodes. Finally, the node with the highest comprehensive degree in each core layer is selected as the seed. However, the seed selection strategy of KT can easily lose some influential nodes. Thus, by optimizing the seed selection strategy, this paper proposes an efficient heuristic algorithm called improved K-shell in temporal social networks for influence maximization (KTIM). According to the hierarchical distribution of cores, the algorithm adds nodes near the central core to the candidate seed set. It then searches for seeds in the candidate seed set according to the comprehensive degree. Experiments show that KTIM is close to the best performing improved method for influence maximization of temporal graph (IMIT) algorithm in terms of effectiveness, but runs at least an order of magnitude faster than it. Therefore, considering the effectiveness and efficiency simultaneously in temporal social networks, the KTIM algorithm works better than other baseline algorithms.     

Semi-GSGCN: Social Robot Detection Research with Graph Neural Network

Malicious social robots are the disseminators of malicious information on social networks, which seriously affect information security and network environments. Efficient and reliable classification of social robots is crucial for detecting information manipulation in social networks. Supervised classification based on manual feature extraction has been widely used in social robot detection. However, these methods not only involve the privacy of users but also ignore hidden feature information, especially the graph feature, and the label utilization rate of semi-supervised algorithms is low. Aiming at the problems of shallow feature extraction and low label utilization rate in existing social network robot detection methods, in this paper a robot detection scheme based on weighted network topology is proposed, which introduces an improved network representation learning algorithm to extract the local structure features of the network, and combined with the graph convolution network (GCN) algorithm based on the graph filter, to obtain the global structure features of the network. An end-to-end semi-supervised combination model (Semi-GSGCN) is established to detect malicious social robots. Experiments on a social network dataset (cresci-rtbust-2019) show that the proposed method has high versatility and effectiveness in detecting social robots. In addition, this method has a stronger insight into robots in social networks than other methods.     

Influence Diffusion Model in Multiplex Networks

The problem of influence maximizing in social networks refers to obtaining a set of nodes of a specified size under a specific propagation model so that the aggregation of the node-set in the network has the greatest influence. Up to now, most of the research has tended to focus on monolayer network rather than on multiplex networks. But in the real world, most individuals usually exist in multiplex networks. Multiplex networks are substantially different as compared with those of a monolayer network. In this paper, we integrate the multi-relationship of agents in multiplex networks by considering the existing and relevant correlations in each layer of relationships and study the problem of unbalanced distribution between various relationships. Meanwhile, we measure the distribution across the network by the similarity of the links in the different relationship layers and establish a unified propagation model. After that, place on the established multiplex network propagation model, we propose a basic greedy algorithm on it. To reduce complexity, we combine some of the characteristics of triggering model into our algorithm. Then we propose a novel MNStaticGreedy algorithm which is based on the efficiency and scalability of the StaticGreedy algorithm. Our experiments show that the novel model and algorithm are effective, efficient and adaptable.     

Anti‐triangle centrality‐based community detection in complex networks

Community detection has been extensively studied in the past decades largely because of the fact that community exists in various networks such as technological, social and biological networks. Most of the available algorithms, however, only focus on the properties of the vertices, ignoring the roles of the edges. To explore the roles of the edges in the networks for community discovery, the authors introduce the novel edge centrality based on its antitriangle property. To investigate how the edge centrality characterises the community structure, they develop an approach based on the edge antitriangle centrality with the isolated vertex handling strategy (EACH) for community detection. EACH first calculates the edge antitriangle centrality scores for all the edges of a given network and removes the edge with the highest score per iteration until the scores of the remaining edges are all zero. Furthermore, EACH is characterised by being free of the parameters and independent of any additional measures to determine the community structure. To demonstrate the effectiveness of EACH, they compare it with the state‐of‐the art algorithms on both the synthetic networks and the real world networks. The experimental results show that EACH is more accurate and has lower complexity in terms of community discovery and especially it can gain quite inherent and consistent communities with a maximal diameter of four jumps.Inspec keywords: biology computing, complex networks, graph theory, social sciences computingOther keywords: antitriangle centrality‐based community detection, complex networks, technological networks, social networks, biological networks, vertex properties, edge roles, community discovery, antitriangle property, community structure, edge antitriangle centrality, isolated vertex handling strategy, EACH, antitriangle centrality scores, synthetic networks, real world networks     

Identification of the influential parts in a complex mechanical product from a reliability perspective using complex network theory

Due to the difference in the numbers and strengths of physical relationships among parts, complex mechanical products (CMPs) have community structure characteristics. There are often some influential parts in the community. Failures of these influential parts spread rapidly along the physical relationships between parts in the community, which seriously affects the reliability of a product. Therefore, identifying the influential parts in the community and adopting targeted measures can effectively improve the reliability and service life of a product. However, identifying the influential parts within each community in a collection of parts with complex relationships is very difficult. Thus, from the perspective of reliability, a method for identifying the influential parts of a CMP based on complex network theory is proposed and used to identify the influential parts in each community of products. First, weighted complex network (WCN) theory is employed to construct a CMP into a WCN model. Second, the complex network community detection method is employed to detect the community structure of the WCN model. Third, a modified LocalRank algorithm is employed to identify the influential nodes in each community, ie, the influential parts in each community of a CMP. Fourth, a modified susceptible-infectious-recovered (SIR) model is employed to evaluate the impacts of the influential parts. An analysis of a company's DC drill planetary gearbox shows that the proposed method is accurate and effective.     

WISECODE: wise image segmentation based on community detection

Image segmentation is one of the fundamental problems in image processing and computer vision, since it is the first step in many image analysis systems. This paper presents a new perspective to image segmentation, namely, segmenting input images by applying efficient community detection algorithms common in social and complex networks. First, a common segmentation algorithm is used to fragment the image into small initial regions. A weighted network is then constructed. Each initial region is mapped to a vertex, and all these vertices are connected to each other. The similarity between two regions is calculated from colour information. This similarity is then used to assign weights to the edges. Afterwards, a community detection algorithm is applied, and communities are extracted such that the highest modularity measure is achieved. Finally, a post-processing algorithm merges very small regions with the greater ones, further enhancing the final result. One of the most striking features of the proposed method, is the ability to segment the input image without the need to specify a predefined number of segments manually. This remarkable feature results from the optimal modularity value, which is utilised by this method. It is also able to segment the input image into a user defined number of segments. Extensive experiments have been performed, and the results show that the proposed scheme can reliably segment the input colour image into good subjective criteria.     

Detection of local community structures in complex dynamic networks with random walks

Identification of interaction patterns in complex networks via community structures has gathered a lot of attention in recent research studies. Local community structures provide a better measure to understand and visualise the nature of interaction when the global knowledge of networks is unknown. Recent research on local community structures, however, lacks the feature to adjust itself in the dynamic networks and heavily depends on the source vertex position. In this study the authors propose a novel approach to identify local communities based on iterative agglomeration and local optimisation. The proposed solution has two significant improvements: (i) in each iteration, agglomeration strengthens the local community measure by selecting the best possible set of vertices, and (ii) the proposed vertex and community rank criterion are suitable for the dynamic networks where the interactions among vertices may change over time. In order to evaluate the proposed algorithm, extensive experiments and benchmarking on computer generated networks as well as real-world social and biological networks have been conducted. The experiment results reflect that the proposed algorithm can identify local communities, irrespective of the source vertex position, with more than 92% accuracy in the synthetic as well as in the real-world networks.     

Recommender systems using cluster-indexing collaborative filtering and social data analytics

As a result of the extensive variety of products available in e-commerce settings during the last decade, recommender systems have been highlighted as a means of mitigating the problem of information overload. Collaborative filtering (CF) is the most widely used algorithm to build such systems, and improving the predictive accuracy of CF-based recommender systems has been a major research challenge. This research aims to improve the prediction accuracy of CF by incorporating social network analysis (SNA) and clustering techniques. Our proposed model identifies the most influential people in an online social network by SNA and then conducts clustering analysis using these people as initial centroids (cluster centres). Finally, the model makes recommendations using cluster-indexing CF based on the clustering outcomes. In this step, our model adjusts the effect of neighbours in the same cluster as the target user to improve prediction accuracy by reflecting hidden information about his or her social community. The experimental results indicate that the proposed model outperforms other comparison models, including conventional CF, with statistical significance.     

Collaborative Filtering Recommendation Algorithm Based on Multi-Relationship Social Network

Recommendation system is one of the most common applications in the field of big data. The traditional collaborative filtering recommendation algorithm is directly based on user-item rating matrix. However, when there are huge amounts of user and commodities data, the efficiency of the algorithm will be significantly reduced. Aiming at the problem, a collaborative filtering recommendation algorithm based on multi-relational social networks is proposed. The algorithm divides the multi-relational social networks based on the multi-subnet complex network model into communities by using information dissemination method, which divides the users with similar degree into a community. Then the user-item rating matrix is constructed by choosing the k-nearest neighbor set of users within the community, in this case, the collaborative filtering algorithm is used for recommendation. Thus, the execution efficiency of the algorithm is improved without reducing the accuracy of recommendation.     

Wireless multicasting under probabilistic node failures: a heuristic approach

The minimum power multicast (MPM) problem is a well-known optimization problem in wireless networks. The aim of the MPM problem is to assign transmission powers to the nodes of a wireless sensor network in such a way that multi-hop communication between a source node and a set of destination nodes is guaranteed, while the total transmission power expenditure over the network is minimized. Several extensions to the basic problem have been proposed, in order to obtain more realistic mathematical models. In this paper we deal with the probabilistic minimum power multicast (PMPM) problem, where node failure probabilities are considered and a global reliability level of the transmission is required. Since the so far available exact approach can handle only small-sized instances of the PMPM problem, in this paper we focus on the study of a heuristic approach. A heuristic algorithm for the PMPM problem is presented, together with a fast method for the reliability calculation based on previously unexplored combinatorial properties of the model. Computational experiments are finally discussed.     

MINE: A Method of Multi-Interaction Heterogeneous Information Network Embedding

Interactivity is the most significant feature of network data, especially in social networks. Existing network embedding methods have achieved remarkable results in learning network structure and node attributes, but do not pay attention to the multiinteraction between nodes, which limits the extraction and mining of potential deep interactions between nodes. To tackle the problem, we propose a method called MultiInteraction heterogeneous information Network Embedding (MINE). Firstly, we introduced the multi-interactions heterogeneous information network and extracted complex heterogeneous relation sequences by the multi-interaction extraction algorithm. Secondly, we use a well-designed multi-relationship network fusion model based on the attention mechanism to fuse multiple interactional relationships. Finally, applying a multitasking model makes the learned vector contain richer semantic relationships. A large number of practical experiments prove that our proposed method outperforms existing methods on multiple data sets.     

Integer programming‐based method for observability of singleton attractors in Boolean networks

Boolean network (BN) is a popular mathematical model for revealing the behaviour of a genetic regulatory network. Furthermore, observability, an important network feature, plays a significant role in understanding the underlying network. Several studies have been done on analysis of observability of BNs and complex networks. However, the observability of attractor cycles, which can serve as biomarker detection, has not yet been addressed in the literature. This is an important, interesting and challenging problem that deserves a detailed study. In this study, a novel problem was first proposed on attractor observability in BNs. Identification of the minimum set of consecutive nodes can be used to discriminate different attractors. Furthermore, it can serve as a biomarker for different disease types (represented as different attractor cycles). Then a novel integer programming method was developed to identify the desired set of nodes. The proposed approach is demonstrated and verified by numerical examples. The computational results further illustrates that the proposed model is effective and efficient.Inspec keywords: integer programming, Boolean algebra, complex networks, diseasesOther keywords: disease, consecutive nodes, biomarker detection, attractor cycles, complex networks, genetic regulatory network, mathematical model, Boolean networks, singleton attractors, integer programming‐based method     

A scheduling scheme for wireless sensor networks based on social insect colonies

Sensor networks employ a large amount of wireless sensor nodes to provide sensing power with high redundancy. Such redundancy makes sensor networks robust under changing environments. However, without proper scheduling, the surplus sensing power will cost tremendous energy consumption to the wireless sensor nodes. A scheduling scheme based on social insect colonies is proposed here. The proposed scheme is a kind of adaptive 'periodic on-off' scheduling scheme that uses only local information for making scheduling decisions. The scheme is evaluated in terms of averaged detection delay, target 3-coverage hit-rate and energy consumption per successful target detection. Simulation results show that, when comparing with other generic scheduling schemes, the proposed scheme can reduce energy consumption from a minimum of 7.49% to a maximum of 90.81% and improve the target hit-rate from a minimum of 15.7% to a maximum of 58.9%. Optimisation of the network lifetime and other performances is possible by adjusting some parameters.     

CNR: A Cluster-Based Solution for Connectivity Restoration for Mobile WSNs

Wireless Sensor Networks (WSNs) are an integral part of the Internet of Things (IoT) and are widely used in a plethora of applications. Typically, sensor networks operate in harsh environments where human intervention is often restricted, which makes battery replacement for sensor nodes impractical. Node failure due to battery drainage or harsh environmental conditions poses serious challenges to the connectivity of the network. Without a connectivity restoration mechanism, node failures ultimately lead to a network partition, which affects the basic function of the sensor network. Therefore, the research community actively concentrates on addressing and solving the challenges associated with connectivity restoration in sensor networks. Since energy is a scarce resource in sensor networks, it becomes the focus of research, and researchers strive to propose new solutions that are energy efficient. The common issue that is well studied and considered is how to increase the network’s life span by solving the node failure problem and achieving efficient energy utilization. This paper introduces a Cluster-based Node Recovery (CNR) connectivity restoration mechanism based on the concept of clustering. Clustering is a well-known mechanism in sensor networks, and it is known for its energy-efficient operation and scalability. The proposed technique utilizes a distributed cluster-based approach to identify the failed nodes, while Cluster Heads (CHs) play a significant role in the restoration of connectivity. Extensive simulations were conducted to evaluate the performance of the proposed technique and compare it with the existing techniques. The simulation results show that the proposed technique efficiently addresses node failure and restores connectivity by moving fewer nodes than other existing connectivity restoration mechanisms. The proposed mechanism also yields an improved field coverage as well as a lesser number of packets exchanged as compared to existing state-of-the-art mechanisms.     

Identifying spreading influence nodes for social networks

The identification of spreading influence nodes in social networks, which studies how to detect important individuals in human society, has attracted increasing attention from physical and computer science, social science and economics communities. The identification algorithms of spreading influence nodes can be used to evaluate the spreading influence, describe the node’s position, and identify interaction centralities. This review summarizes the recent progress about the identification algorithms of spreading influence nodes from the viewpoint of social networks, emphasizing the contributions from physical perspectives and approaches, including the microstructure-based algorithms, community structure-based algorithms, macrostructure-based algorithms, and machine learning-based algorithms. We introduce diffusion models and performance evaluation metrics, and outline future challenges of the identification of spreading influence nodes.     

RSS-based Monte Carlo localisation for mobile sensor networks

Node localisation is a fundamental problem in wireless sensor networks. Many applications require the location information of sensor nodes. Received signal strength (RSS) is a simple and inexpensive approach for localisation purpose. However, the accuracy of RSS measurement is unpredictable owing to the nature of the radio frequency (RF) channel. An RSS-based Monte Carlo localisation scheme is proposed to sequentially estimate the location of mobile nodes, using the log-normal statistical model of RSS measurement. The RSS measurement is treated as the observation model in Monte Carlo method and the mobility feature of nodes as the transition model. Our method is widely applicable because the RSS function is easy to implement on nodes, and the mathematical model for mobile nodes may have non-analytic forms. Simulation results about localisation accuracy and cost show that this scheme is better than other methods.     

Cost Optimisation for Underground Mining Networks

In this paper we consider the problem of optimising the construction and haulage costs of underground mining networks. We focus on a model of underground mine networks consisting of ramps in which each ramp has a bounded maximum gradient. The cost depends on the lengths of the ramps, the tonnages hauled through them and their gradients. We model such an underground mine network as an edge-weighted network and show that the problem of optimising the cost of the network can be described as an unconstrained non-linear optimisation problem. We show that, under a mild condition which is satisfied in practice, the cost function is convex. Finally we briefly discuss how the model can be generalised to those underground mine networks that are composed not only of ramps but also vertical shafts, and show that the total cost in the generalised model is still convex under the same condition. The convexity of the cost function ensures that any local minimum is a global minimum for the given network topology, and theoretically any descent algorithms for finding local minima can be applied to the design of minimum cost mining networks.This work was supported by the Australian Research Council     

Internet practice and professional networks in Chilean science: Dependency or progress?

The conventional view depicts scientific communities in the developing world as globally isolated and dependent. Recent studies suggest that individual scientists tend to favor either local or international ties. Yet there are good reasons to believe that both kinds of ties are beneficial for knowledge production. Since they allow for the more efficient management of social networks, Internet technologies are expected to resolve this inverse relationship. They are also expected to decentralize access to resources within developing regions that have traditionally reflected an urban male bias. Elaborating upon science, development and social network perspectives, we examine the impact of the Internet in the Chilean scientific community, addressing the questions ‘to what extent is Internet use and experience associated with the size of foreign and domestic professional networks?’ and ‘are professional network resources equitably distributed across regional and demographical dimensions?’ We offer results from a communication network survey of 337 Chilean researchers working in both academic departments and research institutes. We introduce a new measure, ‘collaboration range’, to indicate the extent to which scientists engage in work with geographically dispersed contacts. Results suggest that larger foreign networks are associated with higher email use and diversity, but local networks are smaller with longer use of the Internet. Diversity of email use is also associated with diverse geographical networks. Moreover, Internet use may be reducing the significance of international meetings for scientific collaboration and networking. Finally, results also show that in the Internet age professional network resources are distributed symmetrically throughout the Chilean scientific community.