Network sampling is the task of selecting a subset of nodes and links from a network in a way that preserves its topological properties and other user requirements. This paper investigates the problem of generating an unbiased network sample that contains balanced proportion of nodes from different groups. Creating such a representative sample would require handling the trade-off between ensuring structural preservability and group representativity of the selected nodes. We present a novel max-min subgraph fairness measure that can be used as a unifying framework to combine both criteria. A greedy algorithm is then proposed to generate a fair and representative sample from an initial set of target nodes. A theoretical approximation guarantee for the output of the proposed greedy algorithm based on submodularity and curvature ratios is also presented. Experimental results on real-world datasets show that the proposed method will generate more fair and representative samples compared to other existing network sampling methods.

Graph neural networks (GNNs) have emerged as a powerful tool for modeling graph data due to their ability to learn a concise representation of the data by integrating the node attributes and link information in a principled fashion. However, despite their promise, there are several practical challenges that must be overcome to effectively use them for node classification problems. In particular, current approaches are vulnerable to different kinds of biases inherent in the graph data. First, if the class distribution is imbalanced, then the GNNs' loss function is biased towards classifying the majority class correctly rather than the minority class, which hurts the performance of the latter class. Second, due to homophily effect, the learned representation and subsequent downstream tasks may favor certain demographic groups over others when applied to social network data. To mitigate such biases, we propose a novel framework called Fairness-Aware Cost Sensitive Graph Convolutional Network (FACS-GCN) for classifying nodes in networks with skewed class distributions. Our approach combines a cost-sensitive exponential loss with an adversarial learning component to alleviate the ill-effects of both biases. The framework employs a stagewise additive modeling approach to ensure there is no significant loss in accuracy when imparting fairness into the GNN. Experimental results on 6 benchmark graph data demonstrate the effectiveness of FACS-GCN against comparable baseline methods in terms of promoting fairness while maintaining a high model accuracy on the majority of the datasets.

Link prediction is an important task in online social networking as it can be used to infer new or previously unknown relationships of a network. However, due to the homophily principle, current algorithms are susceptible to promoting links that may lead to increase segregation of the network—an effect known as filter bubble. In this study, we examine the filter bubble problem from the perspective of algorithm fairness and introduce a dyadic-level fairness criterion based on network modularity measure. We show how the criterion can be utilized as a postprocessing step to generate more heterogeneous links in order to overcome the filter bubble problem. In addition, we also present a novel framework that combines adversarial network representation learning with supervised link prediction to alleviate the filter bubble problem. Experimental results conducted on several real-world datasets showed the effectiveness of the proposed methods compared to other baseline approaches, which include conventional link prediction and fairness-aware methods for i.i.d data.

Algorithmic fairness is a major concern in recent years as the influence of machine learning algorithms becomes more widespread. In this paper, we investigate the issue of algorithmic fairness from a network-centric perspective. Specifically, we introduce a novel yet intuitive function known as fairness perception and provide an axiomatic approach to analyze its properties. Using a peer-review network as a case study, we also examine its utility in terms of assessing the perception of fairness in paper acceptance decisions. We show how the function can be extended to a group fairness metric known as fairness visibility and demonstrate its relationship to demographic parity. We also discuss a potential pitfall of the fairness visibility measure that can be exploited to mislead individuals into perceiving that the algorithmic decisions are fair. We demonstrate how the problem can be alleviated by increasing the local neighborhood size of the fairness perception function.

OFDMA femtocell is a promising technology to improve indoor cellular network coverage cost-effectively. Large-scale deployment of femtocells in the urban area is expected to be realized in the near future. However, inter-femtocell interference significantly limits the achievable throughput of an OFDMA femtocell system, which calls for interference management tailored for femtocell networks. A typical approach to mitigate inter-femtocell interference is known as resource isolation, which aims at assigning non-overlapping resources to interfering femtocells. One of the main challenges for interference mitigation in femtocell networks is that end consumers often install the femtocells. Very limited information about the femtocells is available, making it hard to decipher the inter-femtocell interference. Previous studies either take time to resolve collisions online or adopt a conservative approach to identify interferers. Although the latter approach avoids wasting time on resolving collisions, it may result in resource underutilization. In this paper, we propose an efficient method to identify inter-femtocell interference by analyzing the received patterns observed by mobile stations. We conducted experiments on GNU Radio/USRP to demonstrate that the proposed interference identification method can successfully identify real interferers while excluding non-interfering femtocells from suspect femtocells. Based on the proposed interference identification, we propose a weighted vertex-coloring based resource assignment algorithm to allocate resources with better fairness and higher throughput.

The design trade-offs of transceiver hardware are crucial to the performance of wireless systems. In this paper, we present an in-depth study to characterize the surprisingly notable systemic impacts of low-pass filter (LPF) design, which is a small yet indispensable component used for shaping spectrum and rejecting interference. Using a bottom-up approach, we examine how signal-level distortions caused by the trade-off of LPF design propagate to the upper-layers of wireless communication, reshaping bit error patterns and degrading link performance of today's 802.11 systems. Moreover, we propose a novel algorithm that harnesses LPF defects for improving video streaming, which substantially enhances video quality in mobile environments.

Networks provide a powerful representation tool for modeling dyadic interactions among interconnected entities in a complex system. For many applications such as social network analysis, it is common for the entities to appear in more than one network. Network alignment (NA) is an important first step towards learning the entities' behavior across multiple networks by finding the correspondence between similar nodes in different networks. However, learning the proper alignment matrix in noisy networks is a challenge due to the difficulty in preserving both the neighborhood topology and feature consistency of the aligned nodes. In this paper, we present OPTANE, a robust unsupervised network alignment framework, inspired from an optimal transport theory perspective. The framework provides a principled way to combine node similarity with topology information to learn the alignment matrix. Experimental results conducted on both synthetic and real-world data attest to the effectiveness of the OPTANE framework compared to other baseline approaches.

Network representation learning algorithms seek to embed the nodes of a network into a lower-dimensional feature space such that nodes that are in close proximity to each other share a similar representation. In this paper, we investigate the effectiveness of using network representation learning algorithms for link prediction problems. Specifically, we demonstrate the limitations of existing algorithms in terms of their ability to accurately predict links between nodes that are in the same or different communities and nodes that have low degrees. We also show that incorporating node attribute information can help alleviate this problem and compare three different approaches to integrate this information with network representation learning for link prediction problems. Using five real-world network datasets, we demonstrate the efficacy of one such approach, called SPIN, that can effectively combine the link structure with node attribute information and predict links between nodes in the same and different communities without favoring high degree nodes.

Existing collaborative ranking based recommender systems tend to perform best when there is enough observed ratings for each user, and the observed data is uniformly sampled at random. However, when the observed ratings are extremely sparse (e.g. in the case of cold-start item where no rating data is available), and are not sampled uniformly at random, existing ranking methods fail to effectively leverage side information to transduct the knowledge from existing ratings to unobserved ones. We propose a semi-supervised collaborative ranking model, dubbed S2COR, to improve the quality of cold-start item recommendation. S2COR mitigates the sparsity issue by leveraging side information about both observed and missing ratings by collaboratively learning the ranking model. This enables it to deal with the case of data missing not at random, but to also effectively incorporate the available side information in transduction. We experimentally evaluated our proposed algorithm on a number of challenging real-world datasets and compared our results against state-of-the-art models for cold-start recommendation. We show significantly higher quality recommendations with our algorithm when compared to other state-of-the-art methods.

Although recommendation systems based on the latent factor models provide an appealing solution to the collaborative filtering problem, some major issues such as data sparsity and cold-start problems, still remain open. In particular, for a large portion of items that there are not sufficient purchase records, their latent factors cannot be estimated accurately. In this paper, we aim to learn and exploit the preference of users in combination with the latent factor models to mitigate these issues and to improve recommendation accuracy. To this end, we propose a novel algorithm to accurately learn the preference of users from observed ratings and available taxonomy of items. We show that predictions made based on the extracted users' preferences enable to capture the taste of users and generates more effective recommendations than pure latent factor models. To the best of our knowledge, the proposed algorithm is the first to extract and exploit the implicit preference of users in the recommendation. We conduct thorough experiments on real datasets that demonstrate the proposed model improves significantly over state-of-the-art latent factor models.

A subgraph H of a given graph G is isometric if the distances between every pair of vertices in H are the same as the distances of those vertices in G. We say a graph G is distance preserving if there exists an isometric subgraph of every possible order up to the order of G. Distance preserving property has been applied to many real world problems such as route recommendation systems and all kinds of shortest-path-related applications. Here, we propose a biologically-inspired search algorithm to address the problem of finding isometric subgraphs that consequently determines if a given graph is distance preserving. In this algorithm, using a well defined fitness function, selection operator selects almost isometric subgraphs to generate the offspring for the next generation. There is a trade-off between the population size and searching speed. On one hand, the larger the population size is, the slower the search algorithm would be. On the other hand, by increasing the population size, we increase the likelihood of finding an existing isometric subgraph. Experimental results depict the performance of the proposed algorithm in finding isometric subgraphs even for challenging problems, and interestingly by these results one can see that "almost" all graphs are distance preserving. In closing, we show the smallest distance preserving graph whose product factors are not distance preserving. This graph has 80 vertices, and can be used as benchmark for algorithms in this concept.

The design trade-offs of transceiver hardware are crucial to the performance of wireless systems. In this paper, we present an in-depth study to characterize the surprisingly notable systemic impacts of low-pass filter (LPF) design, which is a small yet indispensable component used for shaping spectrum and rejecting interference. Using a bottom-up approach, we examine how signal-level distortions caused by the trade-off of LPF design propagate to the upper-layers of wireless communication, reshaping bit error patterns and degrading link performance of today's 802.11 systems. Moreover, we propose a novel algorithm that harnesses LPF defects for improving video streaming, which substantially enhances video quality in mobile environments.

Although the matrix completion paradigm provides an appealing solution to the collaborative filtering problem in recommendation systems, some major issues, such as data sparsity and cold-start problems, still remain open. In particular, when the rating data for a subset of users or items is entirely missing, commonly known as thecold-startproblem, the standard matrix completion methods are inapplicable due the non-uniform sampling of available ratings. In recent years, there has been considerable interest in dealing with cold-start users or items that are principally based on the idea of exploiting other sources of information to compensate for this lack of rating data. In this paper, we propose a novel and general algorithmic framework based on matrix completion that simultaneously exploits the similarity information among users and items to alleviate the cold-start problem. In contrast to existing methods, our proposed recommender algorithm, dubbed DecRec,decouplesthe following two aspects of the cold-start problem to effectively exploit the side information: (i) the completion of a rating sub-matrix, which is generated by excluding cold-start users/items from the original rating matrix; and (ii) the transduction of knowledge from existing ratings to cold-start items/users using side information. This crucial difference prevents the error propagation of completion and transduction, and also significantly boosts the performance when appropriate side information is incorporated. The recovery error of the proposed algorithm is analyzed theoretically and, to the best of our knowledge, this is the first algorithm that addresses the cold-start problem with provable guarantees on performance. Additionally, we also address the problem where both cold-start user and item challenges are present simultaneously. We conduct thorough experiments on real datasets that complement our theoretical results. These experiments demonstrate the effectiveness of the proposed algorithm in handling the cold-start users/items problem and mitigating data sparsity issue.

This paper investigates the network completion problem, where it is assumed that only a small sample of a network (e.g., a complete or partially observed subgraph of a social graph) is observed and we would like to infer the unobserved part of the network. In this paper, we assume that besides the observed subgraph, side information about the nodes such as the pairwise similarity between them is also provided. In contrast to the original network completion problem where the standard methods such as matrix completion is inapplicable due the non-uniform sampling of observed links, we show that by effectively exploiting the side information, it is possible to accurately predict the unobserved links. In contrast to existing matrix completion methods with side information such as shared subsapce learning and matrix completion with transduction, the proposed algorithm decouples the completion from transduction to effectively exploit the similarity information. This crucial difference greatly boosts the performance when appropriate similarity information is used. The recovery error of the proposed algorithm is theoretically analyzed based on the richness of the similarity information and the size of the observed submatrix. To the best of our knowledge, this is the first algorithm that addresses the network completion with similarity of nodes with provable guarantees. Experiments on synthetic and real networks from Facebook and Google+ show that the proposed two-stage method is able to accurately reconstruct the network and outperforms other methods.

A major challenge in collaborative filtering based recommender systems is how to provide recommendations when rating data is sparse or entirely missing for a subset of users or items, commonly known as the cold-start problem. In recent years, there has been considerable interest in developing new solutions that address the cold-start problem. These solutions are mainly based on the idea of exploiting other sources of information to compensate for the lack of rating data. In this paper, we propose a novel algorithmic framework based on matrix factorization that simultaneously exploits the similarity information among users and items to alleviate the cold-start problem. In contrast to existing methods, the proposed algorithm decouples the following two aspects of the cold-start problem: (a) the completion of a rating sub-matrix, which is generated by excluding cold-start users and items from the original rating matrix; and (b) the transduction of knowledge from existing ratings to cold-start items/users using side information. This crucial difference significantly boosts the performance when appropriate side information is incorporated. We provide theoretical guarantees on the estimation error of the proposed two-stage algorithm based on the richness of similarity information in capturing the rating data. To the best of our knowledge, this is the first algorithm that addresses the cold-start problem with provable guarantees. We also conduct thorough experiments on synthetic and real datasets that demonstrate the effectiveness of the proposed algorithm and highlights the usefulness of auxiliary information in dealing with both cold-start users and items.

The significance of social-enhanced recommender systems is increasing, along with its practicality, as online reviews, ratings, friendship links, and follower relationships are increasingly becoming available. In recent years, there has been an upsurge of interest in exploiting social information, such as trust and distrust relations in recommendation algorithms. The goal is to improve the quality of suggestions and mitigate the data sparsity and the cold-start users problems in existing systems. In this paper, we introduce a general collaborative social ranking model to rank the latent features of users extracted from rating data based on the social context of users. In contrast to existing social regularization methods, the proposed framework is able to simultaneously leverage trust, distrust, and neutral relations, and has a linear dependency on the social network size. By integrating the ranking based social regularization idea into the matrix factorization algorithm, we propose a novel recommendation algorithm, dubbed PushTrust. Our experiments on the Epinions dataset demonstrate that collaboratively ranking the latent features of users by exploiting trust and distrust relations leads to a substantial increase in performance, and to effectively deal with cold-start users problem.

Inter-femtocell interference significantly limits the achievable throughput of an OFDMA femtocell system, which calls for interference management tailored for femtocell net-works. A typical approach to mitigate inter-femtocell interference is known as resource isolation, which aims at assigning nonoverlapping resources to interfering femtocells. One of the main challenges for interference mitigation in femtocell networks is that the femtocells are often installed by end-consumers without any pre-planning. Very limited information about the femtocells is available, making it hard to decipher the inter-femtocell interference. In this paper, we propose an efficient method to identify inter-femtocell interference by analyzing the received patterns observed by mobile stations. We conducted experiments to demonstrate that the proposed interference identification method can successfully identify real interferers while excluding non-interfering femtocells from suspicious interferers. Based on the proposed interference identification, we propose a weighted vertex-coloring based resource assignment algorithm to allocate resources with better fairness and achieve higher throughput.

The Collaborative Process to Align Computing Education with Engineering Workforce Needs (CPACE) team developed a partnership among various stakeholders to identify the computational skills that are essential for a globally competitive engineering workforce. Our goal is to redesign the role of computing within the engineering programs at Michigan State University (MSU) and Lansing Community College (LCC) to develop computational competencies - informed by industry needs - by infusing computational learning opportunities into the undergraduate engineering curriculum. In this paper we summarize the process that we used to translate our research findings about the computational competencies needs in the engineering workplace into fundamental computer science (CS) concepts that can be used in curricular implementation. We also discuss the initial phase of our curricular implementation strategy in two disciplinary engineering programs at MSU and transfer programs at LCC.

Cluster analysis describes the division of a dataset into subsets of related objects, which are usually disjoint. There is considerable variety among the different types of clustering algorithms. Some of these clustering algorithms represent the dataset as a graph, and use graph-based properties to generate the clusters. However, many graph properties have not been explored as the basis for a clustering algorithm. In graph theory, a subgraph of a graph is distance-preserving if the distances (lengths of shortest paths) between every pair of vertices in the subgraph are the same as the corresponding distances in the original graph. In this paper, we consider the question of finding proper distance-preserving subgraphs, and the problem of partitioning a simple graph into an arbitrary number of distance-preserving subgraphs for clustering purposes. We also present a clustering algorithm called DP-Cluster, based on the notion of distance-preserving subgraphs. One area of research that makes considerable use of graph theory is the analysis of social networks. For this reason we evaluate the performance of DP-Cluster on two real-world social network datasets.

The rise of email as a communication medium raises several issues. A majority of email messages sent are spam. Also, the amount of legitimate email received by many users is overwhelming. In this paper, we propose two new methods of performing email prioritization. Both techniques rank users inboxes using models created from email history. With them, lower priority email messages may be dealt with so that the use of email remains a net productivity gain.

Within networks there is often a pattern to the way nodes link to one another. It has been shown that the accuracy of node classification can be improved by using the link data. One of the challenges to integrating the attribute and link data, though, is balancing the influence that each has on the classification decision. In this paper we present a matrix alignment approach to the problem of collective classification which weights the attributes and the links according to their predictive influence. The experiments show that while our approach provides comparable accuracy in prediction to other methods, it is also very fast and descriptive.

Social networks have become a major focus of research in recent years, initially directed towards static networks but increasingly, towards dynamic ones. In this paper, we investigate how different pre-processing decisions and different network forces such as selection and influence affect the modeling of dynamic networks. We also present empirical justification for some of the modeling assumptions made in dynamic network analysis (e.g., first-order Markovian assumption) and develop metrics to measure the alignment between links and attributes under different strategies of using the historical network data. We also demonstrate the effect of attribute drift, that is, the importance of individual attributes in forming links change over time.

This paper introduces a new discriminative learning technique for link prediction based on the matrix alignment approach. Our algorithm automatically determines the most predictive features of the link structure by aligning the adjacency matrix of a network with weighted similarity matrices computed from node attributes and neighborhood topological features. Experimental results on a variety of network data have demonstrated the effectiveness of this approach.

Communities are nodes in a network that are grouped together based on a common set of properties. While the communities and link structures are often thought to be in alignment, it may not be the case when the communities are defined using other external criterion. In this paper we provide a new way to measure the alignment. We also provide a new metric that can be used to estimate the number of communities to which a node is attached. This metric, along with degree, is used to assign a community-based role to nodes. We demonstrate the usefulness of the community-based node roles by applying them to the influence maximization problem.

In unstructured peer-to-peer (P2P) systems, there exists a serious topology mismatch problem between physical and logical network. We first analyze the relationship between the property of the overlay and the corresponding message duplications incurred by queries in a given overlay, and prove that computing an optimal overlay with global knowledge is an NP-hard problem. Motivated by the analysis results, we design a distributed overlay optimization algorithm, THANCS, to attack topology mismatch. We demonstrate its performance by comprehensive simulations in dynamic environments. The proposed THANCS has three major strengths. First, it does not need any global knowledge. Second, its optimization convergent speed is fast. Third, it is orthogonal with other types of advanced search approaches.

Implementing multicast in MANETs is a challenging task. A typical multicast network consists of a single tree, in which only a few internal nodes contribute most resources and are involved in performing the multicast functionality. This leads to an un-even utilization of network resources. This problem is more prominent in MANETs where network resources are limited. A possible solution to the problem is to split the multicast content over a number of trees. Multiple trees provide several paths for the multicast content and get more nodes involved in implementing the multicast functionality. However, in such a setup, not all the trees get to use the best weight edges, thus the overall multicast latency increases. This paper presents MEST, a distributed algorithm to construct multiple edge-sharing trees for small group multicast. MEST balances the resource allocation and delay constraints by choosing to overlap certain edges that have low weights. Our simulation results show that MEST is scalable and can generate multicast networks that have low delay and fair resource utilization.

Overlay networks have made it easy to implement multicast functionality in wireless ad hoc networks. Their flexibility to adapt to different environments has helped in their steady growth. In MANET, the position of nodes constantly changes; as a result, overlay multicast trees that are built using location information to account for node movement would certainly have a low latency. However, the performance gains of such a tree are offset by the overhead involved in maintaining precise location information. As the degree of (location) accuracy increases, the performance improves but the overhead required to store and broadcast this information also increases. In this paper, we present SOLONet, a design to build a sub-optimal location aided overlay multicast tree, where location updates of each member node are event based. Our simulation results indicate that such a sub-optimal tree does not compromise the performance gains of a location aided overlay multicast tree.

This paper presents a new handoff protocol named HOPOVER (HandOff Protocol for OVERlay networks). This protocol is compatible with Mobile IP and is designed specifically for overlay networks where handoffs happen both horizontally and vertically. Handoff performance is enhanced by a number of measurements including pre-reserving resources, packet buffering in the new network and packet forwarding from the old network to the new network. Our simulation proved the effectiveness of these measurements.

Peer-to-peer file systems are typically vulnerable to denial-of-service or free-loader problems. Those that address these issues employ approaches that are either simplistic or require a centralized authority. We explore how a zero-sum trading system can provide strong quotas to a peer-to-peer distributed file system without any centralized authority. We treat each member of such a peer-to-peer system as an autonomous agent, interested in preserving its own disk storage. We develop a model for these agents, and present experimental simulation and external emulation results from a multi-agent reinforcement learning model demonstrating the validity of this approach.

Dispersity multicasting is an extension of dispersity routing for multicast communication. In dispersity multicasting, m arc-disjoint subtrees are used for source-destination message delivery. If the bottleneck flow control is applied to each of the m arc-disjoint subtrees, there might still exist extra bandwidth for the multicast communication. To exploit the extra bandwidth, we introduce the concept of virtual connections. We design a flow control algorithm for the available-bit-rate dispersity multicasting with two arc-disjoint subtrees and one virtual connection. Issues in applying the algorithm to ATM networks are discussed. Simulation studies show that, in general, our algorithm enhances the throughput of dispersity multicasting.

In this paper, we study a combination of the multicast communication problem and the maximum disjoint paths problem. Specifically, we are given a directed tree T rooted at r, and we want to send a message from r to a subset of nodes in T. We accomplish this via a multicast schedule which consists of a number of time steps in which informed nodes deliver the message to uninformed nodes until all destinations have received the message. In each time step, any informed node s may forward the message to one of its uninformed descendant nodes d via the unique directed path, or dipath, p from s to d in ditree T. A multicast schedule is called edge-disjoint if the dipaths used in any time step do not share any edges. We call a multicast schedule a node-disjoint schedule if the dipaths used in any time step are node-disjoint. We show that directed trees can be used to represent source-limited inclusive routing, a realistic class of routing schemes used in popular direct network systems. We then show that node-disjoint multicast schedules in directed trees can be used to closely approximate optimal edge-disjoint multicast schedules. In addition, we show that node-disjoint multicast in directed trees can be reduced to an equivalent broadcast problem in directed trees. We describe an O(n2) greedy algorithm (GA) for performing node-disjoint broadcast in directed trees. The greatest advantages of the GA algorithm are its simplicity and its optimal performance in popular topologies such as meshes, tori, and hypercubes. We also describe an O(n3) algorithm that always produces minimum-length node-disjoint broadcast schedules for directed tree topologies, which can be easily transformed into an algorithm that produces edge-disjoint multicast schedules that are no more than twice the length of an optimal edge-disjoint multicast schedule for an arbitrary topology. © 2000 John Wiley & Sons, Inc.

An important part of secure multicast is key management. Up to now, no completely satisfying scheme has been proposed, which might explain why secure multicast is not used extensively. In this paper, we discuss some representative solutions to the key management problem and summarize the advantages and disadvantages of them. Then we propose a new scheme, secure transmission backbone (STB), which provides a general solution for both secure multicast and unicast. In our method, a secure transmission backbone is constructed. With such a backbone, it is no longer necessary for each individual multicast group to maintain keys. The key management problem is thus solved/avoided completely. STB avoids using global keys and protects transmissions on each hop using local keys. STB is based on existing routing protocols, and it is highly robust, reliable and cost effective.

In this paper, we give a general technique for computing optimal multicast calling schedules in any multiprocessor system that utilizes a direct network interconnection structure as long as a few simple conditions are satisfied. Since almost any real system will satisfy these conditions, this result essentially means that multicast can always be performed in [log(d+1)] phases where d is the number of multicast destinations. In particular, previous results on optimal multicast algorithms in specific direct network topologies are simply corollaries of our result.

Multicast communication, in which the same message is delivered from a source node to an arbitrary number of destination nodes, is being increasingly demanded in parallel computing. System supported multicast services can potentially offer improved performance, increased functionality, and simplified programming, and may in turn be used to support various higher-level operations for data movement and global process control. This paper presents efficient algorithms to implement multicast communication in wormhole-routed direct networks, in the absence of hardware multicast support, by exploiting the properties of the switching technology. Minimum-time multicast algorithms are presented for n-dimensional meshes and hypercubes that use deterministic, dimension-ordered routing of unicast messages. Both algorithms can deliver a multicast message to m-1 destinations in [log/sub 2/ m] message passing steps, while avoiding contention among the constituent unicast messages. Performance results of implementations on a 64-node nCUBE-2 hypercube and a 168-node Symult 2010 2-D mesh are given.>

Abstract A natural communication problem in a multicomputer system, such as the hypercube, is that a processor (called the source) wants to send a message to a number of other processors (destinations). A message‐routing paradigm for such a multidestination communication has been formulated as finding a subgraph called an Optimal Communication Tree (OCT). We prove that the problem of finding an OCT is NP‐hard for the n‐cube graph as well as for a graph whose maximum degree is at most three. Heuristics for finding suboptimal communication trees for the hypercube multicomputer are discussed.

In topological design of multicomputer systems (e.g., the hypercube), the edge- and vertex-connectivities have traditionally been used as deterministic measures of fault-tolerance. These measures have been noted to have some deficiencies and as a result several generalizations of graph connectivity have been proposed. In this paper, the authors examine some instances of the connectivity generalization proposed by Esfahanian and Hakimi, (1988). This generalization of graph connectivity can be used to model the fault-tolerance analysis of multicomputers in which any set S of the multicomputer components is considered fault free if the set S does not satisfy some given topological property rho . Using this model and different definitions of rho , the authors establish the complexity of analyzing the fault-tolerance of multicomputers.>

It is shown that by exchanging any two independent edges in any shortest cycle of the n-cube (n>or=3), its diameter decreases by one unit. This leads to the definition of a new class of n-regular graphs, denoted TQ/sub n/, with 2/sup n/ vertices and diameter n-1, which has the (n-1)-cube as subgraph. Other properties of TQ/sub n/ such as connectivity and the lengths of the disjoints paths are also investigated. Moreover, it is shown that the complete binary tree on 2/sup n/-1 vertices, which is not a subgraph of the n-cube, is a subgraph of TQ/sub n/. How these results can be used to enhance hypercube multiprocessors is discussed.>

In developing deterministic measures of system-level fault tolerance for multiple-processor systems, it has generally been assumed that any subset of system components (processors or links) can potentially fail at the same time. In the present work, the author generalizes these measures by restricting the potentially faulty sets to some subsets of the system components. Using this model, he presents a fault-tolerance analysis for the n-cube networks that shows that such networks can tolerate up to 2n-3 processor failures and remain connected provided that for each processor p in the network, all the processors which are directly connected to p do not fail at the same time. He also shows that in this situation the diameter of the network may increase only by a constant value. The author presents an O((kn)/sup 2/) time algorithm for determining if the network is disconnected when a set of k faulty processors, k>

A class of communication networks which is suitable for "multiple processor systems" was studied by Pradhan and Reddy. The underlying graph (to be called Shift and Replace graph or SRG) is based on DeBruijn digraphs and is a function of two parameters r and m. Pradhan and Reddy have shown that the node-connectivity of SRG is at least r. The same authors give a routing algorithm which generally requires 2m hops if the number of node failures is ≤(r -1). In this paper we show that the node-connectivity of SRG is (2r - 2). This would immediately imply that the system can tolerate up to (2r - 3) node failures. We then present routing methods for situations with a certain number of node failures. When this number is ≤(r - 2) our routing algorithm requires at most m + 3 + logr m hops if 3 + logr m ≤m. When the number of node failures is ≤(2r - 3) our routing algorithm requires at most m + 5 + logr m hops if 4 + logr m ≤ m. In all the other situations our routing algorithm requires no more than 2m hops. The routing algorithms are shown to be computationally efficient.

Abstract In this paper methods are described that will compute the edge‐connectivity of a graph or a digraph at least twice as fast as the known methods. A study of the computation of the vertex‐connectivity is presented which leads to new algorithms for this purpose or for the purpose of determining if the vertex‐connectivity is at least k. These algorithms compare favorably with Kleitman's, Even's, Even and Tarjan's, and Galil's algorithms.