While it is very reasonable to use a multigraph consisting of multiple edges between vertices to represent various relationships, the multigraph has not drawn much attention in research. To visualize such a multigraph...While it is very reasonable to use a multigraph consisting of multiple edges between vertices to represent various relationships, the multigraph has not drawn much attention in research. To visualize such a multigraph, a clear layout representing a global structure is of great importance, and interactive visual analysis which allows the multiple edges to be adjusted in appropriate ways for detailed presentation is also essential. A novel interactive two-phase approach to visualizing and exploring multigraph is proposed. The approach consists of two phases： the first phase improves the previous popular works on force-directed methods to produce a brief drawing for the aggregation graph of the input multigraph, while the second phase proposes two interactive strategies, the magnifier model and the thematic-oriented subgraph model. The former highlights the internal details of an aggregation edge which is selected interactively by user, and draws the details in a magnifying view by cubic Bezier curves; the latter highlights only the thematic subgraph consisting of the selected multiple edges that the user concerns. The efficiency of the proposed approach is demonstrated with a real-world multigraph dataset and how it is used effectively is discussed for various potential applications.展开更多
Deep space networks,satellite networks,ad hoc networks,and the Internet can be modeled as DTNs(Delay Tolerant Networks).As a fundamental problem,the maximum flow problem is of vital importance for routing and service ...Deep space networks,satellite networks,ad hoc networks,and the Internet can be modeled as DTNs(Delay Tolerant Networks).As a fundamental problem,the maximum flow problem is of vital importance for routing and service scheduling in networks.However,there exists no permanent end-to-end path since the topology and the characteristics of links are time-variant,resulting in a crucial maximum flow problem in DTNs.In this paper,we focus on the single-source-single-sink maximum flow problem of buffer-limited DTNs,followed by a valid algorithm to solve it.First,the BTAG(Buffer-limited Time Aggregated Graph)is constructed for modeling the buffer-limited DTN.Then,on the basis of BTAG,the two-way cache transfer series and the relevant transfer rules are designed,and thus a BTAG-based maximum flow algorithm is proposed to solve the maximum flow problem in buffer-limited DTNs.Finally,a numerical example is given to demonstrate the effectiveness of the proposed algorithm.展开更多
基金supported by the National Natural Science Fundation of China(61103081)
文摘While it is very reasonable to use a multigraph consisting of multiple edges between vertices to represent various relationships, the multigraph has not drawn much attention in research. To visualize such a multigraph, a clear layout representing a global structure is of great importance, and interactive visual analysis which allows the multiple edges to be adjusted in appropriate ways for detailed presentation is also essential. A novel interactive two-phase approach to visualizing and exploring multigraph is proposed. The approach consists of two phases： the first phase improves the previous popular works on force-directed methods to produce a brief drawing for the aggregation graph of the input multigraph, while the second phase proposes two interactive strategies, the magnifier model and the thematic-oriented subgraph model. The former highlights the internal details of an aggregation edge which is selected interactively by user, and draws the details in a magnifying view by cubic Bezier curves; the latter highlights only the thematic subgraph consisting of the selected multiple edges that the user concerns. The efficiency of the proposed approach is demonstrated with a real-world multigraph dataset and how it is used effectively is discussed for various potential applications.
基金supported by the National Science Foundation(Nos.91338115,61231008)National S&T Major Project(No.2015ZX03002006)+2 种基金the Fundamental Research Funds for the Central Universities(Nos.WRYB142208,JB140117)Shanghai Aerospace Science and Technology Innovation Fund(No.201454)the 111 Project(No.B08038).
文摘Deep space networks,satellite networks,ad hoc networks,and the Internet can be modeled as DTNs(Delay Tolerant Networks).As a fundamental problem,the maximum flow problem is of vital importance for routing and service scheduling in networks.However,there exists no permanent end-to-end path since the topology and the characteristics of links are time-variant,resulting in a crucial maximum flow problem in DTNs.In this paper,we focus on the single-source-single-sink maximum flow problem of buffer-limited DTNs,followed by a valid algorithm to solve it.First,the BTAG(Buffer-limited Time Aggregated Graph)is constructed for modeling the buffer-limited DTN.Then,on the basis of BTAG,the two-way cache transfer series and the relevant transfer rules are designed,and thus a BTAG-based maximum flow algorithm is proposed to solve the maximum flow problem in buffer-limited DTNs.Finally,a numerical example is given to demonstrate the effectiveness of the proposed algorithm.
