Due to the rapid proliferation of Android malware, conventional anti-malware signature-based solutions face significant challenges to battle against cybercrime. In this work, we propose to use quantitative data flow profiles between system entities such as processes, files and sockets to detect malicious applications on Android, an approach which has been shown to be promising for detecting Windows malware. Our approach uses features based on graph-theoretical metrics as a basis for the analysis. Those features are trained through multiple machine learning algorithms obtaining malware detection rates of up to 93% for variants of known (trained) families and detection of new families of up to 84%.