In this paper, we argue that discourse representations can be mapped to networks and analyzed by tools provided in network theory so that deep properties of discourse structure are revealed. Two discourse-annotated corpora, C58 and STAC, that belong to different discourse types and languages were compared and analyzed. Various key network indices were used for the discourse representations of both corpora and show the different network profiles of the two discourse types. Moreover, both network motifs and antimotifs were discovered for the discourse networks in the two corpora that shed light on strong tendencies in building or avoiding to build discourse relations between utterances for permissible three-node discourse subgraphs. These results may lead to new types of discourse structure rules that draw on the properties of the networks that lie behind discourse representation. Another important aspect is that the second version of the STAC corpus, which includes nonlinguistic discourse units and their relations, exhibits similar trends in terms of network subgraphs compared to its first version. This suggests that the nonlinguistic context has a significant impact on discourse structure.