Reducing Computational Complexity of Network Analysis using Graph Compression Method for Brand Awareness Effort

Online� social� media� provides� platform� for� social� interactions.� This� platform� produce� large-scale� data� generated� mostly� from� online� conversations.� Network� analysis� can� help� us� to� mine� knowledge� and� pattern� from� the� relationship� between� actors� inside� the� network.� This� approach� has� been� crucial� in� supporting� prediction� and� decision-making� process.� In� marketing� context� such� as� branding� effort,� using� large-scale� conversation� data� is� cheaper,� faster� and� reliable� comparing� mainstream� approaches� such� as� questionnaire� and� sampling.� Social� network� analysis� provides� several� metrics,� which� was� built� with� no� scalability� in� minds,� thus� it� is� computationally� exhaustive.� Some� metrics� such� as� centrality� and� community� detections� has� exponential� time� and� space� complexity.� With� the� availability� of� cheap� but� large-scale� data,� our� challenge� is� how� to� measure� social� interactions� based� on� those� large-scale� data.� In� this� paper,� we� present� our� approach� to� reduce� the� computational� complexity� of� social� network� analysis� metrics� based� on� graph� compression� method� to� solve� real� world� brand� awareness� effort.�